SWEA

출처 SWEA 1249 보급로 접근 시간복잡도 계산 N <= 100, 지도의 최대 크기가 10000이므로, 방문 체크만 잘 해주면 완전탐색을 하는데 큰 문제가 없는 조건입니다. BFS BFS(너비우선 탐색)를 통해 최단경로를 구할 수 있습니다. 이 때, 미로찾기 알고리즘처럼 목적지에 도착하면 끝나는 것이 아니라, 가중치가 가장 낮은 경로로 이동해야 합니다. 따라서, 이미 목적지에 도착했더라도 더 빠른 경로가 있기 때문에 BFS를 종료하면 안됩니다. 위 그림에서 우 -> 하 순으로 탐색을 진행할 경우, 전체 비용이 6인 경로가 먼저 탐색되지만 비용이 가장 작은 경로는 아닙니다. 이를 위해, 각 지점마다 도달할 수 있는 최소 가중치를 저장해두고, 해당 가중치보다 작은 값만 재방문이 가능하도록 하여 방문 횟수를 줄일 수 있습니다. ...