[백준] 2585번 : 경비행기

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

2585번: 경비행기

해당 문제는 이분탐색 + 너비우선탐색으로 문제를 해결하였습니다. 이분탐색의 mid는 기름통의 크기로 선정 하였고 기름통이 크면 클수록 들러야 하는 수가 적어지게되나 속도가 느려진다. 기름통이 작아지면 들러야하는 수가 많아지나 속도가 빨라진다. 해당 문제를 최적화 하기위해서는 기름통을 이분탐색한다. 또한 들어야하는 수를 계산 할때에는 너비우선탐색을 이용하여 최단거리를 구한다.

 

import sys
import math
from collections import deque

def input(): return sys.stdin.readline().rstrip()

def getDistance(x1,y1, x2, y2):
    return int(math.sqrt(math.pow(abs(x1-x2),2) + math.pow(abs(y1-y2),2)))

def getTankSize(distance):
    tank = distance//10
    if distance % 10 != 0:
        tank += 1
    return tank

def GetCango(tanksize):
    visited = [False for _ in range(len(arrival))]
    queue = deque()
    queue.append([0,0,0]) #자기자신
    visited[0] = True
    result = 0
    while queue:
        x,y, count = queue.popleft()
        if x == 10000 and y == 10000:
            return True
        
        if count > k:
            continue
        
        for i in range(len(arrival)):
            if count <= k:
                if tanksize >= getTankSize(getDistance(x, y, arrival[i][0], arrival[i][1])) and not visited[i]:
                    visited[i] = True
                    queue.append([arrival[i][0], arrival[i][1], count+1])
    
    return False
        
    

distance = getDistance(0,0,10000,10000)
tank = getTankSize(distance)

start = 1
end = tank

n, k = map(int, input().split())

arrival = []
arrival.append([0,0])
for _ in range(n):
    arrival.append(list(map(int, input().split())))

arrival.append([10000,10000])
minresult = 1000
while start <= end:
    mid = (start + end) // 2 # 기름통크기
    
    #print(mid, cango)
    if GetCango(mid): # 급유횟수가 클경우, 기름통을 늘린다.
        minresult = mid
        end = mid - 1
    else: # 급유횟수가 작을경우, 기름통을 줄인다.
        start = mid + 1
        
print(minresult)