[BOJ] 백준 2585번 문제 풀이 (Python)

1. 문제 풀이

이분탐색과 BFS를 이용해서 풀었다.

BFS만 사용해서 문제를 풀 수 없었다. BFS만 사용할 경우$\frac{N!}{(N-K)!}$ 번 탐색을 해서 시간초과가 발생할 수 있기 때문이다.

이분 탐색을 이용해 최소 연료통 용량을 구하면서 BFS 할 때마다 이동할 수 있는 거리에 제한을 두는 방식으로 시간 안에 통과할 수 있었다.

2. 코드

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def cal_dist(n1,n2):
    distance = ((coordinate[n1][0] - coordinate[n2][0])**2 + (coordinate[n1][1] - coordinate[n2][1])**2)**(1/2)
    return int((distance // 10) + 1 if distance % 10 else (distance // 10))

def check(limit):
    visited = set([0])
    q = deque([(0,0)])
    while q:
        w, cnt = q.popleft()
        if dist[w][n+1] <= limit:
            return True
        if cnt >= k: continue
        for nxt in range(n+2):
            if nxt not in visited and dist[w][nxt] <= limit:
                visited.add(nxt)
                q.append((nxt,cnt+1))
    return False

n, k = map(int, input().split())
coordinate = [(0,0)] + [tuple(map(int,input().split())) for _ in range(n)] + [(10000,10000)]
dist = [[0] * (n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        dist[i][j] = cal_dist(i,j)

left, right = 0, cal_dist(0,n+1)
result = 0
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        result = mid
        right = mid - 1
    else:
        left = mid + 1
print(result)