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

 


1. 문제

https://programmers.co.kr/learn/courses/30/lessons/49189

2. 풀이

  • BFS 를 이용해서 가장 마지막의 높이에 존재하는 노드의 개수를 세어주면 됩니다.
from collections import deque

def solution(n, edge):
    answer = 0
    road = {}
    is_visited = [False] * (n + 1)
    for a, b in edge: ## 갈 수 있는 길을 dictionary 를 이용하여 표현
        if a not in road:
            road[a] = []
        if b not in road:
            road[b] = []
        road[a].append(b)
        road[b].append(a)

    queue = deque([1])
    while len(queue): # 최종적으로 BFS가 끝나기 전까지 수행합니다.
        this_round = set()  # 한 높이의 노드들을 확인합니다.
        while len(queue):
            pop_node = queue.popleft()
            this_round.add(pop_node)
            is_visited[pop_node] = True
        answer = len(this_round)  # 해당 높이의 노드들의 개수를 정답으로 넣습니다.
        this_round = list(this_round)
        while len(this_round):    # 노드들을 하나씩 빼면서 방문하지 않은 다음 노드들을 queue에 넣습니다. 
            this_node = this_round.pop()
            for _to in road[this_node]:
                if is_visited[_to] is False:
                    queue.append(_to)

    return answer