[백준/2585] 경비행기 (Python)

Problem : https://www.acmicpc.net/problem/2585

2585번: 경비행기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : ?????

 

---

 

문제 설명

 

 

경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간에 내려서 급유를 받는 횟수가 적은 장점이 있지만 연료통의 무게로 인하여 속도가 느려지고, 안정성에도 문제가 있을 수 있다. 한편 작은 연료통을 장착하면 비행기의 속도가 빨라지는 장점이 있지만 중간에 내려서 급유를 받아야 하는 횟수가 많아지는 단점이 있다. 문제는 중간에 내려서 급유를 받는 횟수가 k이하 일 때 연료통의 최소용량을 구하는 것이다. 아래 예를 보자.

위 그림은 S, T와 7개의 중간 비행장의 위치를 나타내고 있는 그림이다. 위 예제에서 중간급유를 위한 착륙 허용 최대횟수 k=2라면 S-a-b-T로 가는 항로가 S-p-q-T로 가는 항로 보다 연료통이 작게 된다. 왜냐하면, S-p-q-T항로에서 q-T의 길이가 매우 길어서 이 구간을 위해서 상당히 큰 연료통이 필요하기 때문이다. 문제는 이와 같이 중간에 최대 K번 내려서 갈 수 있을 때 최소 연료통의 크기가 얼마인지를 결정하여 출력하면 된다. 참고사항은 다음과 같다.

• 모든 비행기는 두 지점 사이를 반드시 직선으로 날아간다. 거리의 단위는 ㎞이고 연료의 단위는 ℓ(리터)이다. 1ℓ당 비행거리는 10㎞이고 연료주입은 ℓ단위로 한다.
• 두 위치간의 거리는 평면상의 거리이다. 예를 들면, 두 점 g=(2,1)와 h=(37,43)간의 거리 d(g,h)는 sqrt((2-37)^2 + (1-43)^2) = 54.671... 이고 50＜d(g,h) ≤ 60이므로 필요한 연료는 6ℓ가 된다.
• 출발지 S의 좌표는 항상 (0,0)이고 목적지 T의 좌표는 (10000,10000)으로 모든 입력 데이터에서 고정되어 있다.
• 출발지와 목적지를 제외한 비행장의 수 n은 3 ≤ n ≤ 1000이고 그 좌표 값 (x,y)의 범위는 0＜x,y＜10000의 정수이다. 그리고 최대 허용 중간급유 횟수 k는 0 ≤ k ≤ 1000이다.
   

 

 

 

입력 및 출력

 

입력

 

첫 줄에는 n과 k가 하나의 공백을 사이에 두고 주어진다. 그 다음 n개의 줄에는 각 비행장 (급유지)의 정수좌표가 x y 형식으로 주어진다.

 

출력

 

S에서 T까지 k번 이하로 중간급유 하여 갈 수 있는 항로에서의 최소 연료통 용량에 해당되는 정수를 출력한다.

 

입력 예시

 

10 1
10 1000
20 1000
30 1000
40 1000
5000 5000
1000 60
1000 70
1000 80
1000 90
7000 7000

 

출력 예시

 

708

 

 

---

 

풀이

 

모든 경우의 수를 고려하며 단순하게 그래프 탐색으로 풀게 되면 시간 초과를 겪게 된다. 조금 접근을 다르게 해 보아야 한다.

 

• 우선 매개변수를 이용한 이분 탐색을 생각해 볼 수 있겠다. 문제를 "주어진 최대 연료통 i 이하로 경비행기가 시작점에서 끝점으로 도달할 수 있는지"로 설정하자. 최솟값은 0, 최댓값은 시작점에서 끝점으로 바로 가는 경우, 즉 dist((0, 0), (10000, 10000)) = 1415가 된다.
• 다음으로는 위에서 설정한 문제 "주어진 최대 연료통 i 이하로 경비행기가 시작점에서 끝점으로 도달할 수 있는지"를 풀어보자. 단순히 생각해 보면, k이하의 착륙 허용횟수동안 거리가 i 이하인 경로로 비행하여 끝점으로 도달만 가능하면 된다. 즉 bfs로 문제를 해결할 수 있다. 방문 배열 설정을 1차원으로 하되, 방문 배열에 착륙 허용횟수를 저장하도록 하면 더 빠르게 그래프를 탐색할 수 있다.

 

 

풀이 코드

from collections import deque
import math
import sys
input = sys.stdin.readline
MAX = float('inf')

N, K = map(int, input().split())
airport_list = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)] + [(10000, 10000)]

airport_fuel_list = [[0]*(N+2) for _ in range(N+2)]

for i in range(N+1) :
  ix, iy = airport_list[i]
  for j in range(i+1, N+2) :
    jx, jy = airport_list[j]
    fuel = math.ceil(((ix - jx) ** 2 + (iy - jy) ** 2 ) ** 0.5 / 10)
    airport_fuel_list[i][j] = airport_fuel_list[j][i] = fuel

def bfs(value) :
  visited = [-1]*(N+2)
  visited[0] = K
  q = deque([(0, K)])
  while q :
    node, left_landing = q.pop()
    if node == N+1 :
      return True
    if not left_landing :
      if airport_fuel_list[node][-1] <= value :
        return True
      continue
    for i in range(N+2) :
      if i != node and airport_fuel_list[node][i] <= value and left_landing and visited[i] < left_landing-1 :
        visited[i] = left_landing-1
        q.append((i, left_landing-1))
  return False

start, end = 0, 1416
while start < end :
  mid = (start + end) // 2
  if bfs(mid) :
    end = mid
  else :
    start = mid + 1
print(end)

풀이 완료!