[USACO] 숨바꼭질

문제

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.

 

 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

 

입력 조건

- 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 <= N <= 20,000), (1 <= M <= 50000)

- 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 <= A, B <= N)

 

출력 조건

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

 

입력 예시

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

 

출력 예시

4 2 3

---

풀이

 기본적인 그래프 문제라고 볼 수 있습니다. 각각의 헛간을 그래프의 노드로 보고, 1번 노드에서 가장 긴 최단경로로 도달할 수 있는 노드를 찾으면 정답을 찾을 수 있습니다. 특정 노드의 최단 거리를 구하는 문제이므로 다익스트라 알고리즘을 사용하여 쉽게 풀 수 있습니다. 애초에 노드의 개수가 2개 이상 20,000개 이하로 주어졌기 때문에 플로이드-워셜 알고리즘을 적용하면 시간이 너무 오래 걸리기도 하구요. 다음은 소스코드입니다.

 

import heapq

INF = int(1e9)
table = [INF] * (n + 1)

n, m  = list(map(int, input().split()))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    s, e = list(map(int, input().split()))
    graph[s].append(e)
    graph[e].append(s)

def dijkstra(start):
    q = []
    q.append((0, start))
    table[start] = 0
    
    while q:
        cost, now = heapq.heappop(q)
        if table[now] > cost:
            continue
        for i in graph[now]:
            new_cost = cost + 1
            if table[i] > new_cost:
                table[i] = new_cost
                heapq.heappush(q, (new_cost, i))

dijkstra(1)

max_dist = -1
for i in range(1, n + 1):
    d = table[i]
    if d > max_dist:
        max_dist = d
        max_node = i
        cnt = 1
    elif d == max_dist:
        cnt += 1
        
print(max_node, max_dist, cnt)

 

 input을 받는 과정은 매번 동일합니다. 다만 문제의 조건을 조금 상세히 읽을 필요가 있습니다. 문제에서 "하나의 통로는 서로 다른 두 헛간을 연결합니다"라고 했으므로 해당 그래프는 양방향 그래프여야 합니다. 따라서 시작 지점과 종료 지점, 그리고 종료 지점과 시작 지점을 잇는 간선에 대해 모두 graph변수에 초기화해줍니다.

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    s, e = list(map(int, input().split()))
    graph[s].append(e)
    graph[e].append(s)

 

 이후 초기화된 그래프에 대해서 다익스트라 알고리즘을 수행해줍니다. 이때 신경쓸 것은 제시된 모든 간선에 대해서 비용은 1이라는 점입니다. 따라서 기준 노드의 비용에 1을 더해준 것이 연결된 노드까지의 비용입니다. 따라서 다음과 같이 전역변수 table을 업데이트시켜줍니다.

def dijkstra(start):
    q = []
    q.append((0, start))
    table[start] = 0
    
    while q:
        cost, now = heapq.heappop(q)
        if table[now] > cost:
            continue
        for i in graph[now]:
            new_cost = cost + 1
            if table[i] > new_cost:
                table[i] = new_cost
                heapq.heappush(q, (new_cost, i))

dijkstra(1)

 

 이제 초기화된 테이블을 이용하여 정답을 출력해주면 됩니다. 1부터 n + 1까지의 인덱스를 순회하여 기존에 -1로 초기화한 "가장 큰 최단거리"와 비교합니다. 순차 탐색으로 최대값을 도출할 수 있는 것은 "전체 맵이 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어진다"는 조건 덕분입니다. 만약 어떤 헛간의 비용이 INF(infinity)라면, 그 값이 가장 큰 최단거리가 되거나, 혹은 따로 예외처리를 해주어야겠죠.

 그리고 같은 값을 만나면 가장 큰 최단거리가 같은 노드가 있다는 의미이므로 카운팅해줍니다. cnt변수는 따로 초기화를 해주지 않았는데, max_dist를 -1으로 주었을 경우 어떤 노드에서부터 탐색을 시작해도 -1보다는 큰 비용이 나오므로 자동으로 cnt를 1로 초기화해주기 때문입니다.

max_dist = -1
for i in range(1, n + 1):
    d = table[i]
    if d > max_dist:
        max_dist = d
        max_node = i
        cnt = 1
    elif d == max_dist:
        cnt += 1
        
print(max_node, max_dist, cnt)

---

여담

 "특정 노드의 최단 거리를 구하는 문제에는 다익스트라 알고리즘을 쓴다"라는 건 제가 정의한 것이긴 한데, 지금까지 한번도 예외가 되는 케이스가 나오지 않았기 때문에 어느정도 합당한 말로 보아도 괜찮을 것 같습니다. 다익스트라 알고리즘에 관한 포스팅은 링크를 따로 걸어두겠습니다.

 

링크: https://jcy1996.tistory.com/29

다익스트라(Dijkstra) 알고리즘