Problem Solving

문제 https://www.acmicpc.net/problem/7490 풀이 DFS 문제이다. 3가지 연산자 (" ", "+", "-")를 배치하는 모든 경우의 수를 수식으로 만든 후 계산하면 된다. 코드 import Foundation func calcuate() { var rawExpression = "" for idx in 0..<n - 1 { rawExpression += String(seq[idx]) rawExpression += cal[idx] } rawExpression += String(seq[n - 1]) let expression = rawExpression.replacingOccurrences(of: " ", with: "") var numbers = [Int]() var operators = [Character]() var numBuffer = "" for element in expression { if element.isNumber { numBuffer.append(element) } else { numbers.append(Int(numBuffer)!) operators.append(element) numBuffer = "" } } if let lastNumber = Int(numBuffer) { numbers.append(lastNumber) } var result = numbers[0] for idx in 0..<operators.count { if operators[idx] == "-" { result -= numbers[idx + 1] } else { result += numbers[idx + 1] } } if result == 0 { print(rawExpression) } } func dfs() { if cal.count == n - 1 { calcuate() return } for op in [" ", "+", "-"] { cal.append(op) dfs() cal.removeLast() } } let t = Int(readLine()!)! var n = Int() var seq = [Int]() var cal = [String]() for _ in 0..<t { n = Int(readLine()!)! seq = Array(1...n) cal = [] dfs() print() }

문제 https://www.acmicpc.net/problem/4179 풀이 지훈이가 움직이고, 불을 퍼뜨리면 된다. 순서대로 진행하면 되는데 주의해야 할 점이 두 가지 있다. 1분마다 기준으로 번갈아서 움직여야 한다. 지훈이가 움직이기 전에 불에 타면 안된다. 코드 from collections import deque def bfs(jihun, fires): is_jihun_Visited = [[-1] * c for _ in range(r)] fire_queue = deque() jihun_queue = deque() fire_queue.append(fires) jihun_queue.append([jihun]) is_jihun_Visited[jihun[0]][jihun[1]] = 0 while jihun_queue or fire_queue: if jihun_queue: jihun_temp_queue = [] jihun_nodes = jihun_queue.popleft() for cur in jihun_nodes: if graph[cur[0]][cur[1]] == "F": continue for move in [(-1, 0), (0, 1), (1, 0), (0, -1)]: next = (cur[0] + move[0], cur[1] + move[1]) if next[0] == -1 or next[1] == -1 or next[0] == r or next[1] == c: return is_jihun_Visited[cur[0]][cur[1]] + 1 if next[0] < 0 or next[0] >= r or next[1] < 0 or next[1] >= c: continue if is_jihun_Visited[next[0]][next[1]] != -1: continue if graph[next[0]][next[1]] == ".": jihun_temp_queue.append(next) is_jihun_Visited[next[0]][next[1]] = is_jihun_Visited[cur[0]][cur[1]] + 1 if jihun_temp_queue: jihun_queue.append(jihun_temp_queue) if fire_queue: fire_temp_queue = [] fire_nodes = fire_queue.popleft() for cur in fire_nodes: for move in [(-1, 0), (0, 1), (1, 0), (0, -1)]: next = (cur[0] + move[0], cur[1] + move[1]) if next[0] < 0 or next[0] >= r or next[1] < 0 or next[1] >= c: continue if graph[next[0]][next[1]] == ".": fire_temp_queue.append(next) graph[next[0]][next[1]] = "F" if fire_temp_queue: fire_queue.append(fire_temp_queue) return "IMPOSSIBLE" r, c = map(int, input().split()) graph = [] for _ in range(r): graph.append(list(input())) jihun = (0, 0) fires = [] for row in range(r): for column in range(c): if graph[row][column] == "J": jihun = (row, column) elif graph[row][column] == "F": fires.append((row, column)) print(bfs(jihun, fires))

문제 https://www.acmicpc.net/problem/2668 풀이 문제를 간단하게 표현하면 그래프 내의 사이클을 모두 찾은 다음에, 사이클에 포함되는 노드을 모두 출력하면 된다. 사이클을 찾으려면 그래프내의 모든 노드에서 dfs를 쓰면 되는데 다음과 같은 케이스들로 나눌 수 있겠다. 1. 사이클에 도달하긴 하나 시작 노드는 사이클에 포함되지 않는 케이스 주어진 예제에서 2번, 4번, 6번, 7번 노드가 해당한다. 탐색을 시작한 노드에서 사이클에 도달하긴 하나, 시작한 노드는 사이클에 포함되지 않는다. 최적화를 위해 이러한 케이스에도 사이클만 따로 분리해 중복되는 연산을 줄일 수 있겠지만, 이 문제의 n이 큰 수가 아니므로, 그냥 아무런 행동도 하지 않는다. ...

문제 https://www.acmicpc.net/problem/14719 풀이 스택 문제이다. 빗물은 양 옆이 블록으로 막혀있을 때, 낮은 블록의 높이를 기준으로 그 사이에 빗물이 고이게 된다. 따라서 스택을 하나 만들고 인덱스 순서대로 입력받은 다음에, “현재까지” 가장 높게 쌓여있던 블록의 높이(currentMax)와 같거나 더 높게 쌓여있는 블록이 스택에 들어오려 할 때, 스택에 쌓여있는 모든 블록들을 빼내면서 고여있는 물의 양을 더하면 된다(currentMax - 중간 블록의 높이). 하지만 이러한 방법을 쓰면 문제점이 하나 있는데, 블록이 계속 커진다는 보장이 없기 때문에, 마지막에 있는 블록들이 붕 뜨게 된다. 이 때는 스택을 뒤집어서 해결하면 된다. 현재 currentMax보다 더 큰 수가 앞에 존재하지 않는다면 뒤집힌 스택은 무조건 currentMax가 마지막에 존재하게 된다. (만약 currentMax보다 낮은 블록은 이미 pop된 상태일 것이기 때문에) 따라서 스택을 뒤집은 다음(혹은 다른 스택에 차례대로 옮긴 후에) 이 전의 과정을 한번 반복하면 문제가 해결된다. ...

문제 https://www.acmicpc.net/problem/17266 풀이 가로등 간의 최대 간격을 찾으면 되는 문제이다. 일반적인 가로등 간의 간격과, 시작점과 첫 가로등의 간격, 도착점과 마지막 가로등의 간격을 알아내면 된다. 가로등 사이의 간격은 양 사이드 모두가 가로등이기 때문에 간격에서 2를 나눠줄 필요가 있다. 이 문제에는 작은 함정이 하나 있는데, 가로등 사이의 간격이 만약 홀수인 경우에는 2로 나눴을 때 0.5가 내림 되기 때문에 주의해야 한다. 코드 import Foundation let n = Int(readLine()!)! let m = Int(readLine()!)! let x = readLine()!.split(separator: " ").map { Int($0)! } var answer = max(x.first!, n - x.last!) for idx in 1..<m { let interval = Int(ceil(Double(x[idx] - x[idx - 1]) / 2.0)) if interval > answer { answer = interval } } print(answer)

문제 https://www.acmicpc.net/problem/14891 풀이 상황 설명이 굉장히 난해하고 비직관적이므로 글을 잘 읽어야 한다. 문제를 겨우 이해하고 나면 알고리즘이나 구현 능력 자체는 크게 요구하지 않는다. 글을 이해하는것 자체가 이 문제의 가장 큰 난관이다. 이 문제에서 톱니바퀴는 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 돌아간 상태의 이전 톱니바퀴가 아닌 돌기 전의 이전 톱니바퀴의 상태로 판단해야 한다. 코드 class Gear(): def __init__(self, stat): self.__stat = stat self.__top = 0 self.__left = 6 self.__right = 2 def rotate(self, drct): self.__top = (self.__top - drct) % 8 self.__left = (self.__left - drct) % 8 self.__right = (self.__right - drct) % 8 @property def top(self): return self.__stat[self.__top] @property def left(self): return self.__stat[self.__left] @property def right(self): return self.__stat[self.__right] def left_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num - 1, 0, -1): if gears[next_gear].right != gears[cur_gear].left: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break def right_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num + 1, 5): if gears[next_gear].left != gears[cur_gear].right: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break gear1 = Gear(list(map(int, input()))) gear2 = Gear(list(map(int, input()))) gear3 = Gear(list(map(int, input()))) gear4 = Gear(list(map(int, input()))) gears = [None, gear1, gear2, gear3, gear4] k = int(input()) answer = 0 rotate_queue = [] for _ in range(k): num, drct = map(int, input().split()) rotate_queue.append((num, drct)) left_shift(num, drct) right_shift(num, drct) for g, d in rotate_queue: gears[g].rotate(d) rotate_queue = [] rank = 1 for idx in range(1, 5): answer += gears[idx].top * rank rank *= 2 print(answer)

문제 https://www.acmicpc.net/problem/14890 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 정방향으로 우선 순회한다. 다음에 있는 칸의 높이가 현재 칸보다 같으면 count를 하나 늘리고(count는 경사로를 지을 수 있는지 판단할 때 사용한다.) 1 낮으면 일단은 패스(역방향에서 확인한다), 1 높으면 경사로를 설치할 수 있는지 판단한다. 경사로를 설치할 수 있는지 판단하는 기준은 두 가지이다. 일단 경사로를 설치하기 충분한 공간이 확보되었는가 (count로 충분한 공간이 얼마나 있는지를 알 수 있다.), 만약 가능하다면 이미 그곳에 경사로가 설치되어 있지는 않는가(이는 is_built 배열로 추적한다. 하지만 정방향을 먼저 하므로 지금 상황에선 필요 없다.) 역방향으로 순회한다. 정방향과 같지만 정방향을 순회하면서 경사로를 지은 곳을 유의할 필요가 있다. 코드 def check(line): is_built = [False] * n current_height = line[0] count = 1 for idx in range(1, n): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): is_built[idx - back] = True count = 1 else: return False current_height = line[idx] else: return False current_height = line[n - 1] count = 1 for idx in range(n - 2, -1, -1): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): if is_built[idx + back]: return False is_built[idx + back] = True count = 1 else: return False current_height = line[idx] else: return False return True n, l = map(int, input().split()) graph = [] graph_tranposed = [[0] * n for _ in range(n)] answer = 0 for _ in range(n): graph.append(list(map(int, input().split()))) for row in range(n): for column in range(n): graph_tranposed[row][column] = graph[column][row] for idx in range(n): answer += 1 if check(graph[idx]) else 0 answer += 1 if check(graph_tranposed[idx]) else 0 print(answer)

문제 https://www.acmicpc.net/problem/14499 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 적힌 숫자 꼴로 딕셔너리를 하나 더 생성하여 두개의 딕셔너리로 주사위의 방향과 각 면에 적혀있는 숫자를 추적할 수 있다. 코드 import copy def north(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["s", "n", "u", "e", "w", "l"]): dice_drct[new] = original_drct[ori] def south(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["n", "s", "l", "e", "w", "u"]): dice_drct[new] = original_drct[ori] def east(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["w", "e", "n", "u", "l", "s"]): dice_drct[new] = original_drct[ori] def west(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["e", "w", "n", "l", "u", "s"]): dice_drct[new] = original_drct[ori] def change(): if graph[x][y] == 0: graph[x][y] = dice_num[dice_drct["l"]] else: dice_num[dice_drct["l"]] = graph[x][y] graph[x][y] = 0 def check(x, y): if x < 0 or x >= n or y < 0 or y >=m: return False return True n, m, x, y, k = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) orders = list(input().split()) dice_num = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} dice_drct = {"u": 1, "l": 6, "n": 2, "e": 3, "w": 4, "s": 5} for order in orders: isTrue = False if order == "1": if check(x, y + 1): y += 1 east() change() isTrue = True if order == "2": if check(x, y - 1): y -= 1 west() change() isTrue = True if order == "3": if check(x - 1, y): x -= 1 north() change() isTrue = True if order == "4": if check(x + 1, y): x += 1 south() change() isTrue = True if isTrue: print(dice_num[dice_drct["u"]])

문제 https://www.acmicpc.net/problem/12100 풀이 최대 20 * 20 크기의 보드에서 2048 게임을 하는 것이다. 최대 5번의 이동만 한다고 문제에 주어져 있으므로, 모든 경우를 탐색하여 문제를 풀 수 있다. 이 문제에서 주의해야할 점은 다음과 같다. 이동하는 방향에서 가까운 숫자부터 이동해야한다. 한 번의 이동동안 이미 합쳐진 숫자는 다시 합쳐지지 않는다. 이 두가지 조건만 잘 생각하면서 작성하면 된다. 코드 import Foundation func dfs(_ size: Int) { if size == 5 { for row in 0..<n { for column in 0..<n { answer = max(answer, graph[row][column]) } } return } for i in 0..<4 { let currentGraph = graph shift(i) dfs(size + 1) graph = currentGraph } } func shift(_ order: Int) { var isMerged = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) if order == 0 { for row in 0..<n { for column in 0..<n { if graph[row][column] != 0 { var newRow = row while newRow > 0 { if graph[newRow - 1][column] == 0 { let temp = graph[newRow][column] graph[newRow][column] = graph[newRow - 1][column] graph[newRow - 1][column] = temp newRow -= 1 } else if graph[newRow][column] == graph[newRow - 1][column] { if isMerged[newRow - 1][column] { break } let temp = graph[newRow][column] graph[newRow][column] = graph[newRow - 1][column] graph[newRow - 1][column] = temp * 2 graph[newRow][column] = 0 isMerged[newRow - 1][column] = true break } else { break } } } } } } if order == 1 { for column in 0..<n { for row in (0..<n).reversed() { if graph[row][column] != 0 { var newRow = row while newRow < n - 1 { if graph[newRow + 1][column] == 0 { let temp = graph[newRow][column] graph[newRow][column] = graph[newRow + 1][column] graph[newRow + 1][column] = temp newRow += 1 } else if graph[newRow][column] == graph[newRow + 1][column] { if isMerged[newRow + 1][column] { break } let temp = graph[newRow][column] graph[newRow][column] = graph[newRow + 1][column] graph[newRow + 1][column] = temp * 2 graph[newRow][column] = 0 isMerged[newRow + 1][column] = true break } else { break } } } } } } if order == 2 { for row in 0..<n { for column in 0..<n { if graph[row][column] != 0 { var newColumn = column while newColumn > 0 { if graph[row][newColumn - 1] == 0 { let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn - 1] graph[row][newColumn - 1] = temp newColumn -= 1 } else if graph[row][newColumn] == graph[row][newColumn - 1] { if isMerged[row][newColumn - 1] { break } let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn - 1] graph[row][newColumn - 1] = temp * 2 graph[row][newColumn] = 0 isMerged[row][newColumn - 1] = true break } else { break } } } } } } if order == 3 { for row in 0..<n { for column in (0..<n).reversed() { if graph[row][column] != 0 { var newColumn = column while newColumn < n - 1 { if graph[row][newColumn + 1] == 0 { let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn + 1] graph[row][newColumn + 1] = temp newColumn += 1 } else if graph[row][newColumn] == graph[row][newColumn + 1] { if isMerged[row][newColumn + 1] { break } let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn + 1] graph[row][newColumn + 1] = temp * 2 graph[row][newColumn] = 0 isMerged[row][newColumn + 1] = true break } else { break } } } } } } } var n = Int(readLine()!)! var graph = [[Int]]() for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } var answer = 0 dfs(0) print(answer)

문제 https://www.acmicpc.net/problem/13460 풀이 기울이는 방향에 따라서 구슬이 이동하므로, 구슬이 이동할 수 있는 방향은 상하좌우임을 알 수 있다. 이 때, 한 번 기울일 때 마다 구슬의 최종 위치는 하나가 나오므로, BFS를 이용해서 문제를 해결할 수 있다. 문제의 조건을 정리하면 다음과 같다. 한 칸에는 구슬 한 개만 들어갈 수 있다. 한 번 기울이면 구슬이 더 이상 움직이지 못할 때 까지 움직인다. 10번 이하의 횟수로만 기울인다. 1, 2 조건을 조합하면 구슬이 다른 구슬을 만나도 벽을 만난것과 같음을 알 수 있고, 따라서 구슬이 겹친 경우에는 처리를 해줘야 한다. ...