[프로그래머스] (LV3) 가장 먼 노드

Python3

문제 설명

---

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

---

python

import heapq as h
def solution(n, edge):
    inf = 50001
    dist = [inf]*(n+1)
    graph = [[] for _ in range(n+1)]
    nodes = []
    isVisit = [False]*(n+1)
    
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    
    h.heappush(nodes,(0,1))
    
    while nodes:
        cur_dist, cur_node = h.heappop(nodes)
        if isVisit[cur_node] == True: continue
        else: isVisit[cur_node] = True
        dist[cur_node] = cur_dist
        
        for next_node in graph[cur_node]:
            if dist[next_node] > cur_dist+1:
                h.heappush(nodes,(cur_dist+1,next_node))

    return dist.count(max(d for d in dist if d != inf))

설명

---

dijkstra 최단거리 알고리즘의 개념을 잘 알고 있다면 무리없이 풀 수 있는 그래프 문제다.

주어진 간선 그래프를 저장하고, 한 heap queue를 만들어 그곳에 방문하게 될 노드들의 스케줄을 짠다고 생각하편 간편하다. 풀이에서 nodes가 그 역할을 하는데, while문에선 이를통해 다음과 같은 사항을 반복적으로 수행한다.

• nodes에서 heappop()을 통해 현재까지 지나온 거리가 가장 가까운 노드 정보를 뽑는다.
  • 이미 초기화 되지 않았다면 반드시 최단거리가 되므로, dist에 할당하면 된다.
• 뽑은 노드 정보로 방문한다. isVisit을 통해 방문 여부를 체크하고, 첫 방문이 아니면 continue한다.
• 그래프에서 다시 현재 노드와 연결된 간선들의 정보를 가져와 heap queue에 push한다.

이렇게 주어진 dist 결과에서 초기값 inf를 제외한 최대 값의 개수를 찾아 반환하면 된다.