[파이썬] 숨바꼭질

문제

숨바곡질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 1~N 번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 양방향 통로가 M개 존재하며, 하나의 통로는 두개의 헛간을 연결합니다. 전체 맵은 항상 다른 헛간으로 이동이 가능한 형태로 주어집니다. 

00이는 1번 헛간으로부터 가장 멀리 최단 거리가 가장 먼 헛간이 안전하다고 판단합니다. 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 적성하세요.

입력 조건

• 첫째 줄에는 N과 M이 주어지며 공백으로 구분 (2<=N<=20,000) (1<=M<=50,000)
• 이후 줄에는 연결된 헛간의 번호가 공백으로 주어짐

출력 조건

숨어야하는 헛간의 번호(중복시 가장 작은 헛간 번호 출력), 그 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 갯수출력

풀이

import heapq
n,m = map(int,input().split())
INF = int(1e9)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    graph[b].append(a)
    graph[a].append(b)
distance = [INF] * (n+1)

def dijistra():
    start = 1
    q = []
    #시작을 큐에 넣고 거리 0으로
    distance[start] = 0
    heapq.heappush(q,(0,start))
    #큐가 있을 때까지
    while q:
        dist,x = heapq.heappop(q)
        #이미 처리된 적 있는 노드면 무시
        if dist > distance[x]:
            continue
        #큐에서 꺼낸 것과 연결되어 있는 노드 확인
        for i in graph[x]:
            #현재 노드를 거쳐서 가는것이 짧을경우
            cost = dist + 1
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q,(cost,i))

    b = max(distance[1:])
    a = distance.index(b)
    c = distance.count(b)

    print(a,b,c)

dijistra()

'''
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2
'''