전체 글

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 이번 문제는 해결하고도 왜 시간초과 없이 해결이 된 것인지 의아했다. 아니나 다를까 백준에서 문제에 대한 의견들을 찾아보니 나 처럼 이게 풀리다니... 하는 반응이었다. 처음 문제를 봤을 때, 각 섬들에 대해 BFS를 사용하여 마킹을 해두고 각 섬들마다 인접한 바다에서 BFS를 사용해서 최단거리를 brute force로 구하는 것이었다. 그러나 이는 러프하게 계산해도 N^4에 근사한 시간복잡도가 나와 절대 안 풀릴것 같았고 바다에서 BFS를 하는 방법 등 고민을 하다가 우선 처음 생각난 방법대로 구현을 해 보았다. 처음 구상한 방법도 구현 난이도가 쉽지는 않아서 구현 + BFS의 느낌이 강했다. 그런데... 이게 시간초과가 없이 풀려서 나도 놀라웠다. ..

분류 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] ..