[python] 프로그래머스 49189번 : 가장 먼 노드 (BFS)

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

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

 

1. 정답인 코드 

from collections import deque
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [-1]*(n+1)
    
    for v in edge:
        a = v[0]
        b = v[1]
        graph[a].append(b)
        graph[b].append(a)
    for data in graph:
        data.sort()
    # print(graph)
    deq = deque([1])
    # print(deq)
    visited[1] = 0
    while deq:
        node = deq.popleft()
        for next_node in graph[node]:
            if visited[next_node] == -1:
                visited[next_node] = 1 + visited[node] 
                deq.append(next_node)
                
    long_distance = max(visited)
    for data in visited:
        if data == long_distance:
            answer += 1
    return answer

 

graph 리스트 생성시 graph = [[]]*(n+1) 과 같은 방식으로 구현하면

주소값이 복사되어 graph[0],...graph[n-1]이 모두 같은 리스트를 가리키게 된다.

따라서 위에서 구현한 것처럼 graph = [[] for _ in range(n+1)] 와 같은 방식으로 리스트를 각각 생성해주어야 한다.

 

간선에 가중치가 1이므로 BFS를 사용하여 구현할 수 있다.