프로그래머스: 가장 먼 노드

문제

코딩테스트 연습 - 가장 먼 노드

 

문제 풀이

 각 노드의 간선 정보가 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드를 파악하 한 후, 이와 같은 거리를 가진 노드가 몇 개인지 반환하는 문제이다. BFS를 통한 그래프 탐색을 이해하고 있다면 쉽게 풀 수 있는 문제이다.

 

• 그래프의 간선 정보를 하나의 리스트에 초기화 한다.
  • 예를 들어, 1번 노드에서 2번 노드가 접근 가능하다면, `graph[1].append[2]`와 같이 진행하면 된다.
  • 리스트 인덱스에 접근하기 위해 node들에 -1을 하여 처리하였다.
  • 그래프는 양방향이므로, `graph[1].append[2`]라면 `graph[2].append[1]`도 처리해 주어야 한다.
• 방문 여부를 확인하는 `visited`를 활용하여, 현재 노드에 방문하는데 걸린 거리를 체크한다.
• BFS를 통해, 1번 노드를 시작으로 하여 방문 가능한 지점을 탐색한 후 `vistied`에 거리를 체크한다.

 

코드

from collections import deque


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

    # 그래프 연결 정보 초기화.
    for node, connect in edge:
        graph[node - 1].append(connect - 1)
        graph[connect - 1].append(node - 1)

    # visited로 노드 간의 길이를 카운트.
    visited = [0] + [-1] * (n - 1)
    # 첫 번째 시작 노드는 [1번 노드]
    q = deque([[0, 0]])

    while q:
        cur_node, dist = q.popleft()

        for next_node in graph[cur_node]:
            if visited[next_node] == -1:
                q.append([next_node, dist + 1])
                visited[next_node] = dist + 1

    # visited의 max값과 그것을 카운트 한것은 가장 먼 노드의 수.
    return visited.count(max(visited))