Q40. 숨바꼭질

[이코테] 최단 경로 - 숨바꼭질 (tistory.com)

[이코테] 최단 경로 - 숨바꼭질

문제 설명은 위 블로그 참고.

 

음.. 이건 각 간선의 cost를 1로 하고 최단거리가 가장 크게나오는 노드를 찾으면 될거같다. 1번 헛간에서 출발하니까 다익스트라로 풀면될거같고.

 

최단거리 유형은 응용할게 많이 없어서 그런가 이상하게 다른 챕터에 비해 발상하기가 상대적으로 쉬운거같다.

일단 구현해보자.

 

import heapq

N, M = map(int, input().split())

INF = 1e10
mindist = [INF] * (N + 1)
mindist[1] = 0

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)

q = []
heapq.heappush(q, (0, 1))

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

    if mindist[node] < dist:
        continue

    for nxt_node in graph[node]:
        if mindist[nxt_node] > dist + 1:
            mindist[nxt_node] = dist + 1
            heapq.heappush(q, (dist + 1, nxt_node))

safe_node, distance, count = 0, 0, 0
#find safe node
for i in range(N, 0, -1):
    if mindist[i] >= distance:
        distance = mindist[i]
        safe_node = i

for i in range(1, N + 1):
    if mindist[i] == distance:
        count += 1

print(safe_node, distance, count)

 

그렇게 어렵지 않게 구현할 수 있었다. 깔끔한듯? 정답도 볼까

오 정답에서는 마지막에 distance 리스트에서 정답 뽑아내는걸 원스캔으로 했네.

오...