1. 문제 설명

가장 먼 노드

2. 문제 분석

특정 노드에서 가장 거리가 먼 노드의 개수를 그래프 상에서 구하는 문제이다. BSF를 통해 쉽게 풀 수 있다. 이때 큐를 리스트가 아니라 파이썬 모듈 디큐를 활용하면 보다 시간 효율적이다.

1. 주어진 vertex는 양방향 그래프의 간선이다. 이를 통해 각 노드에 연결된 인접 노드 목록을 만들어준다.
2. 1번 노드를 큐에 넣고 BFS를 시작한다.
3. 현재 위치 노드와 인접한 노드 중 미방문한 노드가 있다면 큐에 넣는다. 이때 최단 거리를 기록해야 하므로 이 시점에서 이 노드에 거리를 기록한다.
4. 1번 노드와 연결된 모든 노드를 방문한 이후 가장 긴 거리를 구해 그 수를 카운트한다.

• 각 노드 당 인접한 노드들의 리스트인 nodes를 따로 만들지 않고 vertex를 그대로 사용했는데, 이 경우 if 조건문을 통해 하나씩 인접했는지 여부를 확인해야 하므로 소요 시간이 매우 길고 낭비가 심하다.

3. 나의 풀이

from collections import deque
def solution(n, vertex):
    queue = deque([[1, 0]])
    visited = [True, True] + (n)*[False]
    depths = [0]*(n+1)
    nodes = [[] for _ in range(n+1)]
    # 1번 노드에서의 최소 거리 depths, 각 노드 별 인접한 모든 노드 nodes

    for tail, head in vertex:
        nodes[tail].append(head)
        nodes[head].append(tail)

    while queue:
        cur_node, cur_depth = queue.popleft()
        for next_node in nodes[cur_node]:
            if not visited[next_node]:
                queue.append([next_node, cur_depth+1])
                visited[next_node] = True
                depths[next_node] = cur_depth+1
                # 미방문한 노드 -> 노드 방문, 큐에 넣기, 깊이 기록
    depths.sort(reverse=True)
    max_val = depths[0]
    cnt = 0
    for depth in depths:
        if depth != max_val: break
        cnt += 1
        # 최대 길이 기준으로 카운트
    return cnt