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

(주)그렙

[programmers] 프로그래머스 가장 먼 노드

(Python)

(글쓴날 : 2020.06.10)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 가장 먼 노드

---

1) 문제

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

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

---

2) 풀이 과정

* 시간 복잡도 : O(E log V)

 

n개의 노드가 있는 그래프가 주어질 때, 1번 노드에서 제일 멀리 떨어진 노드가 몇 개인지 구하는 문제입니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

주어지는 간선에 임의적으로 가중치를 1씩 부여한 무향 인접 리스트를 구현한 뒤, 다익스트라를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import heapq
 
def BFS(hq, di, adjList):
    while(hq):
        wei, vec = heapq.heappop(hq)
        
        if di[vec] > wei:
            di[vec] = wei
            
            for w, v in adjList[vec]:
                heapq.heappush(hq, (w+wei,v))
        
def solution(n, edge):
    adjList = [[] for _ in range(n+1)]
    INF = 2147483647
    di = [INF] * (n + 1)
    di[1] = 0
    hq = []
    
    for e in edge:
        adjList[e[0]].append((1,e[1]))
        adjList[e[1]].append((1,e[0]))
    
    for w, v in adjList[1]:
        heapq.heappush(hq,(w,v))
    
    BFS(hq, di, adjList)
    
    maxDistance = 0
    for d in di:
        if d != INF and maxDistance < d:
            maxDistance = d
    
    return di.count(maxDistance)

---