[백준22865] / 가장 먼 곳 - 다익스트라

 

백준22865

 

푼 날짜 : 2024.11.14

푼 문제 : [22865] / 가장 먼 곳

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 찾기 위해 각 친구마다의 거리표를 만들었다.

이후 반복문으로 min값을 뽑아 그 값이 가장 커지는 집을 정답으로 출력한다.

만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다.

 

예제로 그림을 그려보면 다음과 같이 그래프가 그려진다.

 

(내)이해를 돕기위한 그림

 

A, B, C친구의 거리표는 다음과 같이 나타난다.

 

	1	2	3	4	5	6
A(1)	0	1	4	2	4	5
B(2)	1	0	4	3	3	5
C(5)	4	3	7	6	0	2

 

따라서 3번 집일 때 가장 가까운 거리가 4로 다른 집보다 가장 멀기 때문에 답은 3이 된다.

 

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline

N = int(input())
A, B, C = map(int, input().split())

M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    D, E, L = map(int, input().split())
    graph[D].append((E, L))
    graph[E].append((D, L))

def dijkstra(num):
    heap = [(0, num)]
    dist = [float("INF") for _ in range(N+1)]
    dist[num] = 0

    while heap:
        now_cost, now_node = heapq.heappop(heap)
        if dist[now_node] < now_cost: continue

        for next, cost in graph[now_node]:
            all_cost = now_cost+cost

            if dist[next] > all_cost:
                dist[next] = all_cost
                heapq.heappush(heap, (all_cost, next))
    
    return dist

# 각 친구마다 거리 계산 다 해주기
A_lst = dijkstra(A)
B_lst = dijkstra(B)
C_lst = dijkstra(C)

ans = (0, 0)
for i in range(1, N+1):
    # 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 찾기 위함
    min_ = min(min(A_lst[i], B_lst[i]), C_lst[i])
    if ans[0] < min_: ans = (min_, i)
    
print(ans[1])

 

 

오늘도 한 문제 성공 @_@!!!