[프로그래머스] 가장 먼 노드 - 파이썬(python)

 

 

 

나의 풀이

from collections import deque

def solution(n, edge):
    visited = [-1] * (n+1)
    graph = [[] for _ in range(n+1)]
    q = deque()
    
    for x,y in edge :
        graph[x].append(y)
        graph[y].append(x)
    
    q.append(1)
    visited[1] = 0
    
    while q :
        node = q.popleft()
        for i in graph[node] :
            if visited[i] == -1 :
                visited[i] = visited[node] + 1
                q.append(i)
    
    max_cnt = max(visited)
    return visited.count(max_cnt)

• BFS 로 푼 문제이다.
• 1번 노드로부터 최대로 떨어져있는 노드를 구하는 문제이므로, 1번 노드를 맨 처음 큐에 넣고 시작한다.
• 또한, 1번 노드로부터 최단 경로를 구해야 하므로, visited[] 라는 변수로 해당 노드의 방문 여부를 확인한다.
• graph[] 리스트를 통해 x번째 노드와 연결된 모든 노드들을 저장해둔다.

 

• 큐가 빌 때까지 반복문을 돈다.
• 큐에서 가장 먼저 들어가있는 노드를 꺼내고, 해당 노드와 연결된 노드들을 탐색한다. 
• 연결된 노드 중 아직 방문하지 않은 노드에 대해, 현재 노드 + 1이라는 값을 부여하고, 큐에 삽입한다.
• 반복문을 탈출한 후, visited[] 에 담긴 값 중 가장 큰 값이 1과 가장 멀리 떨어져있는 노드의 거리일 것이다.
• 따라서 해당 값을 가진 노드의 개수를 리턴해주면 된다.