백준 6118번 - 숨바꼭질

숨바꼭질 문제 바로 가기

풀이 날짜: 2026-03-17

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())
start = 1
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a,b = map(int, input().split())
    graph[a].append((b,1))
    graph[b].append((a,1))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance[start] = 0

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

max_dist = max(distance[1:])
count = distance[1:].count(max_dist)

for i in range(1,n+1):
    if distance[i] == max_dist:
        print(i, max_dist,count)
        break

문제 핵심 정리

1번 헛간에서 출발하여 모든 헛간까지의 최단 거리를 구한 뒤, 그 중에서 가장 멀리 떨어진 헛간의 번호와 거리, 그리고 그러한 헛간의 개수를 구하는 문제이다. 그래프는 양방향으로 연결되어 있으며, 모든 간선의 비용이 동일하게 1이라는 특징을 가진다.

문제 접근

모든 간선의 비용이 1이기 때문에 BFS로도 해결할 수 있지만, 다익스트라로 풀어봤다. 다익스트라는 우선순위 큐를 이용해 현재까지 가장 짧은 거리의 노드를 기준으로 탐색을 확장하는 방식으로, 다양한 가중치 그래프에서도 활용 가능한 일반적인 최단 경로 알고리즘이다.

그래프 구성

입력으로 주어지는 헛간 간 연결 정보는 양방향이므로, 인접 리스트 형태로 그래프를 구성할 때 양쪽 모두에 간선을 추가해야 한다. 또한 다익스트라를 사용하기 위해 (노드, 비용) 형태로 저장하였으며, 모든 간선의 비용은 1로 설정하였다.

다익스트라 알고리즘

시작 노드인 1번 헛간에서 출발하여 최단 거리를 계산한다. 우선순위 큐에는 (현재까지 거리, 노드 번호)를 저장하며, 매번 가장 짧은 거리의 노드를 꺼내 인접한 노드들을 확인한다. 이미 더 짧은 거리로 방문한 적이 있는 노드는 무시하고, 새로운 경로가 더 짧을 경우 거리 배열을 갱신하고 큐에 다시 넣는 방식으로 진행한다.

거리 배열의 의미

distance[i]는 1번 헛간에서 i번 헛간까지의 최단 거리를 의미한다. 초기에는 모두 무한대로 설정하고, 시작 노드만 0으로 설정한다. 다익스트라 수행이 끝나면, 이 배열에는 각 헛간까지의 최소 이동 횟수가 저장된다.

내가 헷갈렸던 부분

다익스트라 구현 과정에서 (노드, 비용) 형태의 그래프를 순회하며 i[0], i[1]로 접근하는 부분이 처음에는 직관적이지 않았다. 또한 우선순위 큐에서 꺼낸 거리보다 이미 더 짧은 값이 distance 배열에 저장되어 있을 경우 해당 노드를 건너뛰는 조건문의 의미도 처음에는 이해하기 어려웠지만, 이는 불필요한 탐색을 줄이기 위한 핵심 로직이라는 것을 알게 되었다.

Vienna sausage