전체 글

분류 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를 사용해서 최단거리를 brute force로 구하는 것이었다. 그러나 이는 러프하게 계산해도 N^4에 근사한 시간복잡도가 나와 절대 안 풀릴것 같았고 바다에서 BFS를 하는 방법 등 고민을 하다가 우선 처음 생각난 방법대로 구현을 해 보았다. 처음 구상한 방법도 구현 난이도가 쉽지는 않아서 구현 + BFS의 느낌이 강했다. 그런데... 이게 시간초과가 없이 풀려서 나도 놀라웠다. ..

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