[Level3] 가장 먼 노드

🛠 문제

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

👩🏻‍💻 해결 방법

1번 노드에서 각 노드까지의 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 사용했다

소스 코드

import heapq
def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    
    answer = 0
    distance = [int(1e9)] * (n+1)
    distance[1] = 0
    
    q = []
    heapq.heappush(q, (0, 1))
    
    while q:
        d, now = heapq.heappop(q)
        
        if distance[now] < d:
            continue
        
        for i in graph[now]:
            if distance[i] > d + 1:
                distance[i] = d + 1
                heapq.heappush(q, (d + 1, i))
                
    max_value = max(distance[1:])
    for d in distance:
        if d == max_value:
            answer += 1
    return answer

💡 다른 사람의 풀이

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