이것이 코딩테스트다 40 숨바꼭질 (Python)

문제 링크

동빈이는 숨바꼭질을 한다. 1번 헛간으로부터 최단 거리가 가장 먼 헛간에 숨는다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

• N과 M 이 주어진다. (2 <= N <= 20,000) (1 <= M <= 50,000)
• 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 주어진다. (1<= A,B <= N)

---

Test Case

입력
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

출력
4 2 3

---

문제 풀이

평범한 다익스트라 문제인데, 문제의 조건 중 M개의 양방향 통로가 있다는 점을 간과해서 계속 답을 못 찾았다. 코드에서는 a,b를 입력받고 graph[a].append((b,1) 과 graph[b].append((a,1))을 모두 해줘야 하는 점을 놓쳤다.
이런 잘못된 부분을 찾을 때 정답코드를 보고 찾는것이 아니라 제발 스스로 코드를 보고 디버깅하면서 찾자!
그리고 리스트에서 특정원소를 찾는 코드도 기억해두자. list명.count('찾을원소')

---

Source Code

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())


distance = [INF] * (n+1)
distance[0] = -1
graph = [[] for _ in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    graph[a].append((b,1))
    graph[b].append((a,1))

def dijkstra(start):
    q = []
    distance[start] = 0
    heapq.heappush(q,(0,start))

    while q:
        dist, now_node = heapq.heappop(q)
        if distance[now_node] < dist:
            continue
        for i in graph[now_node]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

dijkstra(1)

max_node = 0
max_distance = max(distance)
for i in range(1,n+1):
    if distance[i] == max_distance:
        max_node = i
        break
cnt = distance.count(max_distance)

print(max_node, max_distance, cnt)