백준_6118_숨바꼭질
https://www.acmicpc.net/problem/6118
6118번: 숨바꼭질
문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자. 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸
www.acmicpc.net
해결 방법
> 문제를 보고 플로이드 - 워셜 알고리즘을 이용해 풀어야겠다고 생각했다.
> 플로이드 - 워셜을 이용하여 푸니 '메모리 초과' 에러가 났다.
> 에러의 이유는 플로이드 - 워셜을 이용하면 2차원 배열을 쓰는데 문제의 입력이 거대하여 메모리 초과가 났던것이다.
> 다익스트라 알고리즘을 이용하자!!
> 문제의 조건에서 술래가 무조건 1부터 찾는다고 한다. ---> 노드 1번에 대해 다익스트라를 돌린다.
> 나온 결과를 알맞게 이용한다.
코드
import sys, heapq, copy
input = sys.stdin.readline
INF = float('inf')
def solve(adjacent, K):
prev = [-1] * (len(adjacent) + 1) # predecessor
dist = [INF] * (len(adjacent) + 1) # source로부터의 최소 거리 배열
dist[K] = 0
priority_queue = []
heapq.heappush(priority_queue, [0, K])
while priority_queue:
# 거리가 제일 작은 노드 선택
current_dist, here = heapq.heappop(priority_queue)
# 인접 노드 iteration
for there, length in adjacent[here].items():
next_dist = dist[here] + length
if next_dist < dist[there]:
dist[there] = next_dist
prev[there] = here
heapq.heappush(priority_queue, [next_dist, there])
return dist, prev
if __name__ == "__main__":
num_place, num_loop = map(int, input().split())
K = 1
adjacent = [{} for _ in range(num_place + 1)]
for _ in range(num_loop):
a, b = map(int, input().split())
# 만약 동일한 경로의 간선이 주어질 경우 적은 비용의 간선 선택
if b in adjacent[a]:
adjacent[a][b] = min(adjacent[a][b], 1)
adjacent[b][a] = min(adjacent[b][a], 1)
else:
adjacent[a][b] = 1
adjacent[b][a] = 1
dist, prev = solve(adjacent, K)
copy_dist = copy.deepcopy(dist)
copy_dist.sort()
max_distance = copy_dist[-3]
count = dist.count(max_distance)
index = dist.index(max_distance)
print(index, max_distance, count)