[Python] BOJ(백준) 18352번 - 특정 거리의 도시 찾기

링크

https://www.acmicpc.net/problem/18352

난이도(solved.ac 참고)

실버2

풀이 1: BFS 활용

일반적인 BFS문제와 같으나 방문하지 않았을 경우 방문처리 하고 그 위치까지의 거리를 +1을 해준다. 그 뒤 +1해준 거리가 목표 거리 K와 같아질 경우 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다.

 

풀이 2: 다익스트라 알고리즘 활용

13행 for문 내부 append에서 가중치를 1로 두고 넣었다. 거리와 현재 노드의 위치를 순서대로 힙에서 빼낸 뒤 cost에 현재까지의 거리(dist) + 가중치 를 넣는다. 여기서는 가중치가 1이므로 +1씩만 더해졌다. 현재 distance의 기본값이 10^9이므로 모든 위치에 대해 10^9보다는 당연히 cost가 더 작을 것이다. 이 값을 반영해준다. 그리고 현재까지의 cost(거리+가중치 1)와 j[0](해당 노드의 위치)을 힙에 넣어주는 방식으로 진행을 한다.

 

while문을 마치고 나면 각 노드까지의 최단 경로의 길이가 출력이 되는데, 이 값이 우리가 미리 input으로 넣어둔 k와 같은지 여부를 확인한 뒤 같으면 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다.