[프로그래머스 Lv.3] 가장 먼 노드 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

풀이

3단계 치고 BFS를 사용하는 문제이기 때문에, 풀이 방법이 익숙해 쉽게 풀 수 있었던 것 같다.

 

BFS처럼 큐를 사용해 그래프를 순회하면서 시작 정점(1번 정점)에서부터의 거리를 계산하고, 이 중 거리가 가장 먼 정점들의 수를 세는 방식으로 간단하게 풀이할 수 있다.

from collections import defaultdict, deque

def solution(n, edges):
    graph = defaultdict(list)
    
    for edge in edges: # 간선들을 순회하며, 각 정점에서 어느 정점에 도달할 수 있는지를 저장
        start, end = edge
        graph[start].append(end)
        graph[end].append(start)        
    
    distances = [0 for _ in range(n+1)] # 거리를 저장할 배열, 정점의 번호와 인덱스를 일치시키고 싶어 n+1 칸의 배열 생성 (0번 인덱스 사용하지 않음)
    distances[1] = 1 # 1번 정점에서 1번 정점까지의 거리는 1이라고 가정 (0을 계산하지 않음이라는 플래그로 사용하기 위함)
    queue = deque([1]) # BFS 시작을 위해 1번 정점을 큐에 넣기
    
    while queue: # BFS 시작
        cur = queue.popleft() # 현재 거리를 계산하고 있는 정점
        next_vertexes = graph[cur] # 그래프 상에서 연결된 정점들
        
        for vertex in next_vertexes: # 다음 정점들을 순회하고
            if distances[vertex] == 0: # 아직 계산하지 않은 정점이라면
                queue.append(vertex) # 다음 계산할 정점으로 queue에 넣고
                distances[vertex] = distances[cur] + 1 # 계산한 거리를 표시
                
    cnt = 0
    max_dist = max(distances) # 최대 거리
    for dist in distances:
        if dist == max_dist: cnt += 1 # 최대 거리에 위치하는 정점의 수
        
    return cnt