[백준/Python] 22865번: 가장 먼 곳

문제

https://www.acmicpc.net/problem/22865

22865번: 가장 먼 곳

---

문제 요약

N개의 땅 중에서 한 곳에 자취를 하기 위해 집을 알아보고 있다.

 

세 친구 A, B, C가 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.

 

이 때, 가장 먼 곳은 선택할 집에서 가장 가까운 친구의 집까지의 거리를 기준으로 가장 먼 곳을 의미한다.

 

ex) X 위치에 있는 집에서 A, B, C의 집까지 거리가 각각 3, 5, 4이고, Y 위치에 있는 집에서 A, B, C의 집까지 거리가 각각 5, 7, 2일 때, X와 Y 중 더 먼 곳은 X 위치에 있는 집이다. 

(X에서 가장 가까운 친구의 집까지의 거리는 3, Y에서 가장 가까운 친구의 집까지의 거리는 2이기 때문이다.)

 

땅과 땅 사이를 잇는 M개의 양방향 통행이 가능한 도로의 정보가 주어진다.

 

친구들이 살고 있는 집으로부터 가장 먼 곳을 출력한다.

+ 땅 번호는 1부터 시작한다.

---

코드

from collections import deque
import sys
import heapq
input = sys.stdin.readline

def dijstra(start, costs):
    que = []
    heapq.heappush(que, (0, start))
    costs[start] = 0    

    while que:
        dist, num = heapq.heappop(que)

        if costs[num] < dist:
            continue
        
        for i in graph[num]:
            cost = dist + i[1]
            if cost < costs[i[0]]:
                costs[i[0]] = cost
                heapq.heappush(que, (cost, i[0]))
                
    return costs

n = int(input()) # 자취할 땅 후보 개수

a, b, c = map(int, input().split()) # 친구 A, B, C가 사는 위치

m = int(input()) # 땅과 땅 사이를 잇는 도로의 개수

graph = [[] * (n + 1) for _ in range(n + 1)]

INF = int(1e9)

a_costs = [INF] * (n + 1)
b_costs = [INF] * (n + 1)
c_costs = [INF] * (n + 1)

# 양방향 통행이 가능하므로 graph에 모두 저장
for _ in range(m):
    d, e, l = map(int, input().split())
    graph[d].append((e, l)) # 땅 d와 땅 e를 잇는 도로의 길이 l
    graph[e].append((d, l)) # 땅 e와 땅 d를 잇는 도로의 길이 l

# a, b, c 위치에서 다른 위치까지 거리 저장
a_costs = dijstra(a, a_costs)
b_costs = dijstra(b, b_costs)
c_costs = dijstra(c, c_costs)

res_value = 0
res = 0

# i에서 a, b, c까지의 최단 거리가 가장 먼 위치 탐색
for i in range(1, n + 1):
    value = min(a_costs[i], b_costs[i], c_costs[i])
    if res_value < value:
        res_value = value
        res = i
    elif res_value == value:
        res = min(res, i)
    
print(res)

---

코드 설명

1. 도로의 정보를 입력 받아 graph에 저장한다.+ 양방향 도로이므로 두 번 저장한다.

 

2. 다익스트라 알고리즘을 이용하여 a, b, c 각 위치에서 다른 위치까지 거리를 저장한 배열을 구한다.

 

3. 반복문을 이용하여 위치 i에서 a, b, c까지 최단거리가 가장 먼 위치를 탐색하고 출력한다.