BFS

문제 https://leetcode.com/problems/remove-methods-from-project 풀이 메소드 k에서 시작해서 도달할 수 있는 노드들을 ‘suspicious’ 하다고 했을 때, 이 ‘suspicious’한 메소드들을 k가 직, 간접적으로 호출하는 것을 제외하고도 호출되는 경우가 있는지 확인하고 있다면 전체 메소드를, 없다면 ‘suspicious’한 메소드를 제외하고 리턴하면 된다. 메소드들의 호출 관계가 단방향 엣지 그래프를 이루기 때문에, BFS나 DFS 무엇을 써도 쉽게 k가 직, 간접적으로 호출하는 함수들을 알 수 있다. k에서 시작해서 도달하는 모든 메소드들은 ‘suspicious’ 하기 때문에 방문 여부를 확인하는 배열을 그대로 사용하면 된다. ...

문제 https://codeforces.com/problemset/problem/520/B 풀이 정수 n, m이 주어지고, 연산 2개 (* 2, - 1)을 이용해서 n을 m으로 만드는데 필요한 연산의 최소 개수를 출력하면 된다. $1 <= n, m <= 10^4$ 제약조건과 2배로 만드는 연산을 생각해보면 만들 수 있는 숫자의 개수는 최대 2만개 정도이다. 이 숫자들을 각각을 노드라 생각하면, 연산으로 정의되는 노드간 연결도 명확한 그래프로 생각할 수 있다. 그러면 이 문제는 최단 거리 문제가 되므로 BFS를 사용해서 쉽게 풀 수 있다. 2배 연산이 있으므로 방문 확인 배열의 크기를 m * 2로 잡고 BFS를 하면된다. (방문 확인 배열도 할 겸 거리를 세는 기능도 넣으면 좋다.) ...

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

문제 https://www.acmicpc.net/problem/5558 파파고 번역 올해도 JOI 마을의 치즈 공장이 치즈 생산을 시작하여, 쥐들이 둥지에서 얼굴을 내밀었다. JOI 마을은 동서남북으로 구획 정리되어 있고, 각 구획은 둥지, 치즈 공장, 장애물, 공터 중 하나이다. 쥐들은 둥지에서 출발하여 모든 치즈 공장을 방문 하여 치즈를 한 개씩 먹는다. 이 마을에는 N개의 치즈 공장이 있는데, 모든 공장이 한 종류의 치즈만을 생산한다. 치즈의 단단함은 공장마다 다르고 단단함도 다르다 1부터 N까지의 치즈를 생 산하는 치즈공장이 마침 하나씩 있다. 증가 쥐들의 첫 번째 체력은 1이고, 치즈를 한 개 먹을 때마다 그들의 체력은 1증가 하지만, 쥐들은 자신의 체력보다 더 단단한 치즈를 먹을 수는 없다. 쥐는 동서남북으로 이웃한 구역으로 1분이면 이동할 수 있지만, 장애물 구역에는 들어갈 수 없다. 치즈 공장을 치즈를 먹지 않고 지나갈 수도 있다. 치즈를 다 먹을 때까지 걸리는 가장 짧은 시간을 요구하는 프로그램을 작성하라. 쥐가 치즈를 먹 는 데 걸리는 시간은 무시할 수 없다. 풀이 처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, …, N 순서대로 먹으면 된다. ...

문제 https://www.acmicpc.net/problem/15591 풀이 문제가 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다. 따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해주면 된다. 코드 from collections import deque def bfs(k, v): queue = deque() queue.append((v, 987_654_321)) isVisited = [False] * (n + 1) isVisited[v] = True answer = 0 while queue: cur_node, cur_usado = queue.popleft() for next_node, next_usado in graph[cur_node]: if isVisited[next_node]: continue if cur_usado < next_usado: next_usado = cur_usado if next_usado >= k: queue.append((next_node, next_usado)) isVisited[next_node] = True answer += 1 print(answer) n, q = map(int, input().split()) graph = {} for _ in range(n - 1): pi, qi, ri = map(int, input().split()) if pi in graph: graph[pi].append((qi, ri)) else: graph[pi] = [(qi, ri)] if qi in graph: graph[qi].append((pi, ri)) else: graph[qi] = [(pi, ri)] for _ in range(q): k, v = map(int, input().split()) bfs(k, v)

문제 https://www.acmicpc.net/problem/14226 풀이 현재 상태를 나타내는 변수를 화면에 있는 이모티콘의 개수, 클립보드에 저장되어 있는 이모티콘의 개수로 나타낼 수 있다. 각각의 연산이 모두 1초가 걸리므로 BFS를 사용할 수 있다. BFS를 사용하려면 노드에 방문했는지를 판별할 방법이 필요한데, 여기에선 Array보다는 Set을 쓰는것이 효율적이다. 두 개의 정수가 노드를 구성하므로 2차원 배열을 만들면 되겠지만, 이런 방식으로 한다면 배열의 크기가 너무 커질 뿐더러 효율적인 배열의 크기를 정하기도 머리가 복잡해진다. 따라서 방문한 노드를 Set에 저장해서 contains()함수로 방문 여부를 판단하는 방식을 이용한다. ...

문제 https://www.acmicpc.net/problem/16234 풀이 그래프 각 원소를 전체 탐색하며, BFS를 수행하는 문제이다. 탐색할 수 있는 칸에 대한 제약조건이 문제에 제시되므로, 이에 따라 BFS를 수행하면 된다. 알고리즘은 다음과 같다. 그래프 전체를 순서대로 순회한다. 이 때 칸이 isVisited가 false인 칸에서 bfs를 수행한다. 따라서 isVisited는 전역 변수(혹은 call by reference)가 되어야 한다. bfs로 탐색한 칸은 서로 연합이 가능한 칸이다. bfs 탐색의 조건은 문제에 상세히 적혀있다. 그래프 전체를 순회하며 bfs 탐색을 실시하고 각 칸의 값을 조정하면, 이게 문제에서 말하는 ‘하루’가 지난 것이다. isVisited가 false인 칸만 연합을 수행하므로, 앞선 칸에서 수행한 bfs 탐색이 뒤에 있는 칸에 영향을 끼칠 일은 없다. 1회의 인구 이동이 끝났어도 또 인구 이동이 가능할 수 있다. 따라서 1.을 더 이상 인구이동이 불가능해 질 때까지 수행한다. 코드 import Foundation func bfs(root: (Int, Int)) -> Bool { struct Queue { private var queue = [(Int, Int)]() private var ptr = 0 var isEmpty: Bool { ptr >= queue.count } mutating func insert(v: (Int, Int)) { queue.append(v) } mutating func delete() -> (Int, Int) { let popped = queue[ptr] ptr += 1 return popped } } let moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] var queue = Queue() var union: [(Int, Int)] = [root] var unionPop = graph[root.0][root.1] queue.insert(v: root) isVisited[root.0][root.1] = true while !queue.isEmpty { let node = queue.delete() for move in moves { let newNode = (node.0 + move.0, node.1 + move.1) if newNode.0 < 0 || newNode.0 >= n || newNode.1 < 0 || newNode.1 >= n { continue } if isVisited[newNode.0][newNode.1] { continue } let differ = abs(graph[node.0][node.1] - graph[newNode.0][newNode.1]) if differ >= l && differ <= r { isVisited[newNode.0][newNode.1] = true queue.insert(v: newNode) union.append(newNode) unionPop += graph[newNode.0][newNode.1] } } } let dividedPop = unionPop / union.count for element in union { graph[element.0][element.1] = dividedPop } if union.count > 1 { return true } else { return false } } let nlr = readLine()!.split(separator: " ").map { Int(String($0))! } let (n, l, r) = (nlr[0], nlr[1], nlr[2]) var graph = [[Int]]() for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } var isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) var answer = 0 while true { var isEnd = true for row in 0..<n { for column in 0..<n { if !isVisited[row][column] && bfs(root: (row, column)){ isEnd = false } } } if isEnd { break } isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) answer += 1 } print(answer)

문제 https://www.acmicpc.net/problem/14502 풀이 dfs와 bfs가 합쳐진 문제이다. 벽을 꼭 3개를 세워야 하므로 dfs를 이용하여 벽을 세울 위치를 전체 탐색할 수 있다. 연구소의 크기가 최대 8 * 8 이므로 전체 탐색하는데 큰 문제가 발생하지 않는다. 벽을 세웠으면 bfs를 이용하여 바이러스가 퍼졌을 때의 연구소의 모습을 그린다. 이 때 바이러스가 지나간 자리는 2로 마킹되고, 벽은 바이러스가 지나가지 못하므로 isVisited와 같은 배열이 없어도 이미 지나간 곳임을 알 수 있다. 알고리즘을 순서대로 나타내면 다음과 같다. ...

문제 https://www.acmicpc.net/problem/1726 풀이 로봇이 바라보는 방향에 따라서 갈 수 있는 노드가 달라진다 -> 3차원 그래프다 (세로 m, 가로 n, 높이가 4인) 이 발상만 빠르게 해낸다면 평범한 BFS 문제가 된다. 하나의 노드에서 최대 5개의 노드와 연결이 가능하다(회전 2방향, 전진 3방향) 하지만 2칸 이상 전진했을때, 앞선 칸이 1이면 넘어가지 못한다. (점프를 할 수 없다) 이것만 주의하고 BFS 탐색을 하면 쉽게 결과를 낼 수 있다. 코드 # east 0 west 1 south 2 north 3 from collections import deque def bfs(start): bfsQ = deque() bfsQ.append(start) isVisited[start[0]][start[1]][start[2]] = True count[start[0]][start[1]][start[2]] = 0 while(bfsQ): node = bfsQ.popleft() currentDir = node[2] currentCount = count[node[0]][node[1]][node[2]] if node == end: return currentCount for dir in rotate[currentDir]: if end == [node[0], node[1], dir]: return currentCount + 1 if isVisited[node[0]][node[1]][dir]: continue isVisited[node[0]][node[1]][dir] = True count[node[0]][node[1]][dir] = currentCount + 1 bfsQ.append((node[0], node[1], dir)) if currentDir == 0: moves = [(0, 1), (0, 2), (0, 3)] elif currentDir == 1: moves = [(0, -1), (0, -2), (0, -3)] elif currentDir == 2: moves = [(1, 0), (2, 0), (3, 0)] else: moves = [(-1, 0), (-2, 0), (-3, 0)] for move in moves: row = node[0] + move[0] column = node[1] + move[1] if end == [row, column, currentDir]: return currentCount + 1 if row < 0 or row >= m or column < 0 or column >= n: continue if isVisited[row][column][currentDir]: continue if graph[row][column] == 1: break isVisited[row][column][currentDir] = True count[row][column][currentDir] = currentCount + 1 bfsQ.append((row, column, currentDir)) graph = [] rotate = {0: [2, 3], 1: [2, 3], 2: [0, 1], 3: [0, 1]} m, n = map(int, input().split()) for _ in range(m): graph.append(list(map(int, input().split()))) start = list(map(int, input().split())) end = list(map(int, input().split())) for i in range(3): start[i] -= 1 end[i] -= 1 isVisited = [[[False] * 4 for i in range(n)] for j in range(m)] count = [[[0] * 4 for i in range(n)] for j in range(m)] print(bfs(start))