BFS

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 3차원 상태가 필요한 BFS 문제를 많이 풀다보니 이번 문제도 어렵지 않게 구상이 되었다. 크게 어렵지는 않았으며, 벽 부수고 이동하기와는 달리 K번까지 이동 가능한 부분만 잘 처리하면 된다. 내가 작성한 코드 from sys import stdin from collections import deque K = int(input()) W, H = map(int, input().split()) graph = [] for i in range(H): graph.append(list(map(int, stdin.readline().rstrip().split()))) MX = 1000001 visit = [[[1000001 for k in range(K + 1)] ..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 매우 모범적인 문제라고 생각한다. 기계적으로 BFS를 막 때려맞히는 것이 아니라, BFS의 근본적인 목적 = 그래프 탐색을 이해하고 있는지 스스로 점검을 하기 좋은 문제라고 생각이 된다. 가중치가 모두 동일한 그래프에서 특정 지점에서 특정 지점으로의 최단 경로를 찾을 때 가장 빠른 알고리즘이 BFS이다. 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘 플로이드 와샬 알고리즘 벨만 포드 알고리즘 이렇게 존재하고 저 셋중 가장 빠른 것은 우선순위 큐를 사용한 다익스트라 알고리즘이다. O(Nlogn) 다익스트라 알고리즘은 가중치가 여러개인 경우 사용할 수 있는 가장 빠른 알고리즘이나 가중치가 모두 같다면, BFS가 가장 빠르다 O(N) BFS는 사실 최단경..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 문제 상황에서 시작점과 도착점이 동일하게 주어진 경우를 놓쳐서 여러번 틀린 문제이다. 문제 자체는 그렇게 어렵지 않은 BFS문제이다. 내가 작성한 코드 from collections import deque F, S, G, U, D = map(int, input().split()) graph = [0 for _ in range(F + 1)] search = deque() dx = [U, -D] moves = -1 search.append((S,1)) graph[S] = 1 while search: C, T = search.popleft() if C == G: moves = T - 1 break for i in range(2): nC = C + dx[i] ..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS 유형의 문제는 여러가지 유형이 존재한다. 가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다. 이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것 같다. 문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다. BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다..