[Programmers 49189] 가장 먼 노드

문제

LV2 [Programmers 49189 - 가장 먼 노드]

문제 풀이 방법

최단경로 알고리즘 문제이므로 다익스트라 알고리즘을 이용하여 풀이할 수 있었다.

1. graph와 distance를 각각 N+1만큼 초기화한다.

   graph를 표현하는 방법에는 크게 인접행렬과 인접 리스트 이렇게 2가지가 있는데, 여기서는 인접 리스트를 사용하여 그래프를 표현하였다.

   distance는 1번 노드부터 각 노드까지의 거리를 저장할 배열로 INF(무한)으로 초기화한다.

   N+1개를 생성하는 이유는 노드번호가 1부터 시작하기 때문에 뒤에서 좀 더 가독성 좋은 코드를 쓰기 위해서이다. 그래서 0번째 배열은 사용되지 않는다.

2. 우선순위 큐를 선언하고 (시작노드의 거리, 시작노드)를 큐에 넣어준다.

   매 단계마다 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택해야 되기 때문에 우선순위 큐를 사용한다. 이 때, 우선 순위의 기준은 튜플의 0번째 인덱스(=거리)이다.

3. 큐가 빌때까지 다음을 반복한다.
   1. 큐에서 가장 거리가 짧은 노드(node)를 뽑는다.
   2. 만약 현재 거리 리스트(distance)에서 해당 노드의 거리(distance[node])가 뽑은 노드의 거리(dist)보다 더 작다면 이미 방문했다는 의미이므로 아래를 수행하지 않고 넘어간다.
   3. 뽑은 노드와 인접하게 연결된 노드들을 for문을 돌면서 순회한다.
      1. 현재 노드(node)를 거쳐서 가는 경우의 거리를 계산하여 cost에 저장한다.
      2. 만약, 현재 거리 리스트(distance)보다 cost가 작다면 거리 리스트를 업데이트 해주고, 큐에 (cost, n)를 추가해준다.
4. distance에서 최댓값을 찾고 count함수를 사용하여 최댓값이 몇 개인지 찾는다.

풀이 코드

Python

import heapq

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

def solution(n, edge):
    INF = int(1e9)
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)
    for a,b in edge:
        graph[a].append((b,1))
        graph[b].append((a,1))

    dijkstra(1, graph, distance)
    long_distance = max(distance[1:])
    print(distance)
    return distance.count(long_distance)