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

문제

풀이

거리를 구하는 그래프 문제이다.

다익스트라를 사용해도 되지만, 익숙한 BFS로 풀이해보았다.

우선 딕셔너리(map)을 이용해서 노드마다 연결된 값들을 담아준 다음,

1번 노드부터 deque를 이용해 BFS 탐색하여

이동시마다 거리를 1씩 늘려서 노드마다의 거리를 n_list에 담아주었다.

딕셔너리 안에 list를 추가하는게 번거로웠는데, defaultdict(list)를 이용해서

default 값으로 value값으로 빈 list를 제공받아 쉽게 구현하였다.

 

LV3에 정답률 48퍼인데  백준으로 따지면 대충 실버 1정도 되지않나 싶다.

코드

from collections import deque
from collections import defaultdict
def solution(n, edge):
    dict=defaultdict(list)
    n_list = [0 for  _ in range(n+1)]
    for i in edge:
        dict[i[0]].append(i[1])
        dict[i[1]].append(i[0])
    visited = set()
    q = deque()
    q.append((1,0))
    visited.add(1)
    while q:
        num,g = q.popleft()
        n_list[num] = g
        for i in dict[num]:
            if i not in visited:
                q.append((i,g+1))
                visited.add(i)
    max_num = max(n_list)
    answer = 0 
    for i in n_list:
        if max_num==i:
            answer += 1
        
    return answer