프로그래머스. 가장 먼 노드 파이썬 풀이

프로그래머스. Level 3. 가장 먼 노드 파이썬 풀이

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

BFS와 다익스트라 두가지 방법으로 풀이할 수 있다.

BFS를 사용한 풀이

from collections import deque

def solution(n, edge):
    answer = 0
    
    graph = [[] for i in range(n+1)]
    distance = [0] * (n+1)
    visited = [False] * (n+1)
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    queue = deque([1])
    visited[1] = True
    distance[1] = 0
    
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                distance[i] = distance[v] + 1
        
    max_ = max(distance)
    
    return distance.count(max_)

다익스트라를 사용한 풀이

import heapq

def solution(n, edge):
    answer = 0
    
    INF = int(1e9)
    
    graph = [[] for i in range(n+1)]
    distance = [INF] * (n+1)
    
    for a, b in edge:
        graph[a].append([b, 1])
        graph[b].append([a, 1])
               
    def dijkstra(start):
        q = []
        
        heapq.heappush(q, (0, start))
        distance[start] = 0
        
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
            
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
        
    dijkstra(1)
    
    distance[0] = 0
    temp = max(distance)
    
     
    return distance.count(temp)