[Python] 가장 먼 노드

1. 문제

 

 

 

2. 풀이 과정

방법 1) heapq 이용, 방법 2)를 추천

import heapq as hq
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    distance = [int(1e9)]*(n+1)
    
    for x, y in edge:
        graph[x].append(y)
        graph[y].append(x)
        
    q = []
    hq.heappush(q, (0, 1)) #최소거리, 시작노드 번호
    distance[1] = 0
    while q:
        d, node = hq.heappop(q)
        for n in graph[node]:
            if distance[n] == int(1e9): #방문하지 않은 노드라면
                hq.heappush(q, (d+1, n))
                distance[n] = d+1
    
    return distance.count(max(distance[1:])) #0번째 index를 제외하고 생각

 

방법 2) queue만 이용, 모든 간선의 cost가 1이기 때문에 heapq를 쓸 필요가 없다. 즉, 방문하지 않은 노드들로 가는 cost는 모두 1이기 때문에 queue만 사용해서 풀 수 있다.

INF = int(1e9)
def solution(n, edge):
    graph = [[] for _ in range(n)]
    distance = [INF]*n
    for n1, n2 in edge:
        graph[n1-1].append(n2-1)
        graph[n2-1].append(n1-1)
        
    q = [0]
    distance[0] = 1
    while q:
        node = q.pop(0)
        for n in graph[node]:
            if distance[n] == INF:
                distance[n] = distance[node]+1
                q.append(n)
                
    return distance.count(max(distance))