숨바꼭질

 

 

문제 유형 분석 및 구현

이 문제도 결과적으로 봐야한다.

결과적으로 한 노드에서 어떠한 노드로 가는데 가장 멀리있는 노드들 중에 번호가 작은 노드를 출력하는 문제이다.

처음에는 헷갈렸던 적도 있는 것 같다. 모든 노드와 노드사이의 최단 경로를 구해야하나라고 생각했다.

하지만 최단경로 문제들은 결과적으로 생각해야 한다.

결과적으로 1번 헛간과 가장 먼 거리를 찾는 경우이므로 다익스트라 알고리즘을 이용한다.

 

주의할 점은 양방향 통로라는 점이다. 따라서 입력받을 때, 두 노드 모두 경로 처리해야한다.

 

 

코드

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

start = 1
distance = [INF]*(n+1)
distance[start] = 0
q = []
heapq.heappush(q, [0, start])

max_value = 0
while q:
    dist, now = heapq.heappop(q)
    max_value = max(max_value, dist)
    if distance[now] < dist:
        continue
    for next in graph[now]:
        cost = dist+1
        if distance[next] > cost:
            distance[next] = cost
            heapq.heappush(q, [cost, next])


count = []
for i in range(len(distance)):
    if distance[i] == max_value:
        count.append(i)
print(min(count), max_value, len(count))