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

문제

풀이

전형적인 bfs 문제다.
bfs로 계속해서 노드를 탐색하고 visit 배열에 노드를 방문하기 위해 거친 edge의 개수를 저장해가며 탐색하면 쉽게 답을 구할 수 있다.

풀이 코드

from collections import deque

def solution(n, edge):
    edge.sort(key = lambda x : (x[0], x[1]))
    visit = [0] * (n+1)
    graph = [[] for _ in range(n+1)]
    
    for x, y in edge:
        graph[x].append(y)
        graph[y].append(x)
    
    q=deque([1])
    visit[1] = 1
    
    while q:
        p = q.popleft()
        for i in graph[p]:
            if not visit[i]:
                visit[i] = visit[p] + 1
                q.append(i)
                    
    max_edge = max(visit)
    answer = 0

    for i in visit:
        if i == max_edge:
            answer += 1
                    
                
    
    return answer