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

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

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

 

1부터 시작하여 BFS 알고리즘을 이용하여 구현했다.

 

while 문을 한번 돌 때마다 deque 의 popleft() 함수를 이용하면 1과의 거리가 1씩 늘어나는 번호들의 집합을 얻을 수 있다.

 

from collections import deque, defaultdict

def solution(n, edge):
    answer = 0
    dic = defaultdict(list)
    D = defaultdict(int)
    D[1] = 1
    queue = deque([1])
    
    for i, j in edge:
        dic[i].append(j)
        dic[j].append(i)
    
    while queue:
        answer = len(queue)
        
        for i in range(answer):
            x = queue.popleft()
        
            for j in dic[x]:
                if D[j] == 0:
                    D[j] = 1
                    queue.append(j)

    return answer

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