[Baekjoon Online Judge] 백준 6118번 숨바꼭질(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 6118번 숨바꼭질

(Python)

(글쓴날 : 2020.06.15)

 

---

* Baekjoon Online Judge, 백준 6118번 문제 Python 언어 풀이입니다.

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

---

 

 

백준 6118번 숨바꼭질

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/6118

6118번: 숨바꼭질

---

2) 풀이 과정

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

 

N개의 헛간이 있는 농장에서 숨바꼭질을 할 때, 1번 헛간에서 제일 먼 헛간을 찾는 문제입니다.

단, 답이 여러 개일 경우 번호가 가장 작은 헛간을 답으로 칩니다.

 

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

문제에서 주어지는 이어진 헛간들의 경로를 가중치가 1인 무향 인접 리스트로 구현한 뒤, 다익스트라 알고리즘을 적용해 1번 헛간에서 제일 먼 헛간을 찾아냈습니다.

그 후, 찾아낸 헛간 번호, 해당 헛간까지의 거리, 같은 거리인 헛간의 개수를 출력해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
 
def dij(hq):
    while(hq):
        wei, vec = heapq.heappop(hq)
 
        if dist[vec] > wei:
            dist[vec] = wei
            
            for w, v in adjList[vec]:
                heapq.heappush(hq, (w + wei, v))
 
 
N, M = map(int, input().split())
 
INF = 2147483647
dist = [INF for _ in range(N + 1)]
dist[1] = 0
 
adjList = [[] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
 
    adjList[a].append((1, b))
    adjList[b].append((1, a))
 
hq = []
for w, v in adjList[1]:
    heapq.heappush(hq, (w, v))
 
dij(hq)
 
print(dist.index(max(dist[1:])), max(dist[1:]), dist.count(max(dist[1:])))

---