[프로그래머스/Python] 가장 먼 노드 - Level3

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

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

이 문제는 최단거리를 찾는 문제로 BFS 로 풀 수 있었다. 전형적인 BFS 문제여서 기본적인 BFS 구조만 알고 있다면 쉽게 풀 수 있을 것이다. 최근에 BFS를 공부했어서 쉽게 풀 수 있었던 것 같다.

from collections import deque

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)] # 연결된 노드 정보 그래프
    distance = [-1] * (n+1) # 각 노드의 최단거리 리스트
    
    # 연결된 노드 정보 추가
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
    queue = deque([1]) # BFS를 위한 큐, 출발 노드는 1
    distance[1] = 0 # 출발 노드의 최단거리 0으로 
    # BFS 수행
    while queue:
        now = queue.popleft() # 현재 노드
         
        # 현재 노드에서 이동할 수 있는 모든 노드 확인
        for i in graph[now]:
            if distance[i] == -1: # 아직 방문하지 않은 노드라면
                queue.append(i) # 큐에 추가
                distance[i] = distance[now] + 1 # 최단거리 갱신
    
    # 가장 멀리 떨어진 노드 개수 구하기
    for d in distance:
        if d == max(distance):
            answer += 1
            
    return answer

1. 연결된 노드 정보 그래프(graph) 와 각 노드의 최단거리를 저장하는 리스트(distance) 생성 후 graph에 노드 연결 정보를 추가한다. 간선이 양방향이므로 양쪽으로 추가해줘야 한다.

2. BFS를 위한 큐(queue) 를 생성한다. 출발 노드는 1이므로 미리 출발 노드를 넣어둔다. 출발 노드의 최단거리는 0 으로 만든다.

3. BFS를 수행한다.

    3-1. 현재 노드(now) 를 가져온다.

    3-2. 현재 노드에서 이동할 수 있는 모든 노드를 확인한다. 아직 방문하지 않은 노드라면 queue에 추가하고 최단거리를 갱신한다.

4. 가장 멀리 떨어진 노드 개수를 구한다.