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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

 

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

입력조건

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

출력조건

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

사고과정

• 문제에서 "N개의 헛간, M개의 양방향 도로"를 보고 그래프 데이터를 활용해야 한다는 것을 알았고 "술래는 1번 헛간에서 출발하는데 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간에 숨는다"라는 것을 보고 특정 노드에서 출발해 다른 노드들 까지의 최단 거리를 구하는 다익스트라 알고리즘을 생각했다. 이 때, 약간 주의할 점은 "양방향 도로"이기 때문에 그래프 데이터를 받을 때, a, b 가 주어지면 a -> b, b -> a 모두 반영해주어야 한다. 그리고 도로 비용은 모두 동일하므로 임의로 모든 간선 비용을 1로 정의해준다.
• 이 때 최단 거리가 가장 긴 곳에 숨어야 하니까 최단 거리 테이블을 모두 구하고 그 중에서 가장 원소값이 큰 인덱스(노드)를 구하면 된다.
• 출력 요구사항에 3가지가 있는데, 이를 처리할 때 필자는 선형 탐색을 2번 진행했다. 주어진 N의 범위가 2만이고 2번 진행해봐야 4만이고  다익스트라 알고리즘 시간 복잡도가 $E(logV)$이기 때문에 5만 곱하기 log2만을 하게 되면 약 50만번의 연산이 필요하고 결국 총 54만번의 연산이 필요하다. 그런데 Python 언어의 특성상 1초에 5천만 번 연산을 수행하고 문제 시간 복잡도 제한에 1초라고 적혀있으므로 2번의 선형탐색을 진행했다.
• 풀이를 보니 1번 만의 선형탐색으로도 풀 수 있었다. 이 점은 배워야 할 듯 하다..!

풀이

1. 스스로 푼 풀이

import heapq

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split()) # a - b 연결
    graph[a].append((b, 1))
    graph[b].append((a, 1))
INF = int(1e9)
start = 1  # 시작 노드
distance = [INF] * (n+1)

def dijkstra(start):
    # 시작 노드
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, node = heapq.heappop(q)
        if dist > distance[node]:
            continue
        for next in graph[node]:
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))
    # 1번 헛간으로부터 가장 먼 헛간까지의 거리
    max_dist = -1
    for i in range(1, n+1):
        if distance[i] != INF:
            max_dist = max(max_dist, distance[i])
    # 그 거리와 같은 노드 중 가장 작은 헛간 번호와 헛간의 개수
    node = []
    for i in range(1, n+1):
        if distance[i] == max_dist:
            node.append(i)
    print(node[0], max_dist, len(node))


dijkstra(start)

2. 책 속 풀이(권장)

import heapq

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split()) # a - b 연결
    graph[a].append((b, 1))
    graph[b].append((a, 1))
INF = int(1e9)
start = 1  # 시작 노드
distance = [INF] * (n+1)

def dijkstra(start):
    # 시작 노드
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, node = heapq.heappop(q)
        if dist > distance[node]:
            continue
        for next in graph[node]:
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))
    # 1번 헛간으로부터 가장 먼 헛간까지의 거리
    max_node = 0
    max_dist = 0
    max_node_lst = []
    for i in range(1, n+1):
        if max_dist < distance[i]:
            max_node = i
            max_dist = distance[i]
            max_node_lst = [max_node]
        elif max_dist == distance[i]:
            max_node_lst.append(i)
    print(max_node, max_dist, len(max_node_lst))


dijkstra(start)