[프로그래머스][Python] 가장 먼 노드

문제를 정리해보자.

 

n개의 노드가 있는 그래프가 있다. 각 노드는 1부터 n까지 번호가 적혀있다.

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하자.

 

가장 멀리 떨어진 노드란?

최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드이다.

 

---

 

풀이를 생각해보자.

 

 

프로그래머스 예시

 

 

간선에 가중치가 없다.

따라서 N번 노드와 1번 노드의 최단 경로는 간선이 가장 적은 경로이다.

 

예를 들어, 5번 노드와 1번 노드의 최단 경로는 1 -> 2 -> 5이다.

 

 

 

 

BFS로 최단 경로를 구할 수 있다.

 

---

 

구현해보자.

 

from collections import deque


def solution(n, edge):
    graph = [[] for _ in range(n + 1)]

    for node in edge:
        A, B = node[0], node[1]

        graph[A].append(B)
        graph[B].append(A)

    distance = [0] * n  # 최대 간선 n-1개

    # BFS 구현
    queue = deque([[1, 0]])  # 노드, 트리 깊이
    check = [0] * (n + 1)  # 방문한 노드 확인

    check[1] = 1

    while queue:
        pre_node = queue.popleft()

        node = pre_node[0]
        depth = pre_node[1]

        for next_node in graph[node]:
            if check[next_node] == 0:

                check[next_node] = 1

                queue.append([next_node, depth + 1])
                distance[depth + 1] += 1
    
    # 출력
    for i in range(n-1, -1, -1):
        if distance[i] != 0:
            return distance[i]


solution(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]])

 

 

마지막에는 가장 멀리 있는 노드의 개수를 출력한다.