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

🗃️문제 설명

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 ≤ N ≤ 20,000), (1 ≤ M ≤ 50,000)
이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 ≤ A, B ≤ N)

첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호를 출력합니다.), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

🖥️코드

import sys, heapq
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        v, now = heapq.heappop(q)
        if distance[now] < v:
            continue
        for i in maps[now]:
            cost = v + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

N, M = map(int, input().split())
maps = [[] for _ in range(N+1)]
inf = float('inf')
distance = [inf] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    maps[a].append((b, 1))
    maps[b].append((a, 1))
dijkstra(1)

max_dist = 0
max_node = 0
result = []
for i in range(1, N+1):
    if max_dist < distance[i]:
        max_dist = distance[i]
        max_node = i
        result = [max_node]        
    elif max_dist == distance[i]:
        result.append(i)
print(max_node, distance[max_node], len(result))

🧠아이디어

알고리즘 유형 : 최단 경로 알고리즘(다익스트라)

개선된 다익스트라 알고리즘(힙을 사용)을 사용하여 최단 경로 테이블을 갱신

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 숨바꼭질
모범 답안 - 숨바꼭질