[백준] 1277 발전소

문제

• 1번 발전소와 N번 발전소가 2차원 격좌 좌표 위에 있다.
• 발전소는 전선으로 연결되며 남아 있는 전선 수는 W이고, 
• 어떤 두 발전소 사이의 전선 길이가 M을 초과해서는 안된다.

 

• 1 <= N <= 1000
  1 <= W <= 10,000
  0.0 <= M <= 200,000.0
  -100,000 <= 발전소 좌표 x, y <= 100,000

 

• 첫 줄에 1번 발전소와 N번 발전소를 잇는데 필요한 추가 전선 길이의 최솟값을 1000배하여 출력한다.
  (단, 1000배하고 난 후 나머지 소수는 반올림이 아닌 버림을 한다)

 

풀이

• 2차원 좌표 상에 위치하므로 각 발전소까지 필요한 최소 전선의 길이를 계산할 수 있다.
  => calc_dist 함수를 이용해 각 발전소 사이에 필요한 최소 전선 길이를 계산한다.
• 이미 전선이 연결된 경우는 추가로 필요한 전선이 없는 것이므로 0이라고 볼 수 있다.
• 다익스트라 알고리즘을 이용해 1번에서부터 다른 발전소까지의 최단 거리(최소 전선 길이)를 계산한다 

 

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

def calc_dist(x1, y1, x2, y2) :
    return (abs(x1-x2)**2 + abs(y1-y2)**2) ** 0.5

N, W = map(int, input().split())
M = float(input())
loc = [0] + [tuple(map(int, input().split())) for _ in range(N)]

# 각 발전소까지의 최단 거리 기록
graph = [[] for _ in range(N+1)]
for i in range(1, N+1) :
    for j in range(1, N+1) :
        d = calc_dist(*loc[i], *loc[j])
        if d <= M :
            graph[i].append((j, d))
            graph[j].append((i, d))

# 이미 연결된 전선들
for _ in range(W) :
    a, b = map(int, input().split())
    graph[a].append((b, 0))
    graph[b].append((a, 0))

# 다익스트라 -> 1번에서 N번까지의 최단 경로 구하기
distance = [INF] * (N+1)
distance[1] = 0
h = []
heapq.heappush(h, (0, 1))

while h :
    dist, idx = heapq.heappop(h)
    if distance[idx] < dist : continue

    for nxt, cost in graph[idx] :
        if distance[nxt] > dist + cost :
            distance[nxt] = dist + cost
            heapq.heappush(h, (dist+cost, nxt))

print(int(distance[N]*1000))

 

References

• 백준 최단거리