[프로그래머스 49189 파이썬] 가장 먼 노드 (level 3, BFS)

알고리즘 유형 : BFS
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=python3

소스 코드(파이썬)

from collections import deque

def solution(n, edge):
    answer = 0
    visited = [0]*(n+1)
    dq = deque([1])
    visited[1] = 1
    graph = [[] for _ in range(n+1)]
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    while dq:
        now = dq.popleft()
        
        for adj_node in graph[now]:
            if not visited[adj_node]:
                visited[adj_node] =  visited[now] + 1
                dq.append(adj_node)
    
    return visited.count(max(visited))

풀이 요약

1. path의 길이를 기록하는 BFS 문제이다.

   path 길이는 visited의 값에 1을 계속 더해나가면서 기록하면 된다.

   주의할 점은, 출발 노드의 재방문을 피하고자 visited를 1로 뒀기 때문에 실제 path 길이는 visited의 값에 1을 뺀 값임을 유의하자. 물론 이 문제에선 딱히 중요한 부분은 아니다.

   가중치가 모두 1이기 때문에 굳이 다익스트라를 쓰지 않아도 된다.

배운 점, 어려웠던 점

• 이전에 푼 경험이 있는 유형이라 쉽게 풀었다.