[이것이 코딩테스트다] 숨바꼭질 with python

•  다익스트라 알고리즘을 이용한 풀이

핵심: 1번부터 출발하므로 1번과 연결되어 있는 노드들을 방문하여 최소의 값을 할당해주고

또 연결된 노드들에서 또다른 연결된 노드들과 값을 비교하여 최소의 값을 할당해주는 식으로

bfs와 유사한 형태를 보이는 것을 알 수 있다.

 

import heapq

# 입력, 헛간을 loc라는 배열 리스트로 초기화
n,m=map(int,input().split())
loc=[[]*(n+1) for _ in range(n+1)]

# 헛간의 양방향 연결을 위하여 각각의 방향에 입력받은 값을 추가시키고, 연결되어 있을 때 1을 핟랑해 준다
for _ in range(m):
    start,end=map(int,input().split())
    loc[start].append((end,1))
    loc[end].append((start,1))
start=1

# 최소값을 구하기 위해 무한으로 초기화해준다
distance=[float('inf')]*(n+1)
distance[start]=0

# 다익스트라 알고리즘
def dijkstra(start):
    q=[]
    # 초반 시작은 1부터 시작하므로 0,1을 넣어준다
    heapq.heappush(q,(0,start))

    while q:
        dist,s=heapq.heappop(q)

        if dist>distance[s]:
            continue
        # 연결되어 있는 번호들
        for i in loc[s]:
            # 양방향 연결되어 있을 때
            cost=dist+i[1]
            if distance[i[0]]>cost:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))
dijkstra(start)

max_node=0
max_distance=0
cnt=0

tmp=max(distance[1:])
for i in range(1,n+1):
    if distance[i]==tmp:
        max_node=i
        break

print(max_node,distance[max_node],distance.count(distance[max_node]),end=' ')