BOJ 2585 경비행기

이분 탐색으로 풀면되는 문제이다. 하지만 조금 까다로워 보이는 것이 있다.
바로 최대 허용 중간급유 횟수 k이다.  연료통의 최소 용량을 구하기 위해서는 k번의 급유를 다 이용하는 것이 좋을 것이다.

일단, 이분 탐색을 이용해서 연료통의 용량을 정하고 그 용량으로 k번이하의 급유를 해서 시작점부터 도착점까지 갈 수 있는지를 따져봐야 하는데, 시작점부터 도착점까지 갈 수 있는지를 따져보는 것이 까다롭다....고 생각했다.  k때문에...

dfs나 bfs를 사용하면 될 것인데, 문제는 어디서 급유를 할 것인가... 즉, k번의 급유를 어떤 비행장에서 써야할 것인가...였다.
주어진 연료의 양으로 k번 이하의 급유를 해서 도착점까지 가려면 연료통에 연료가 남아있어 다음 비행장까지 갈 수 있다면 급유를 하지 않고 계속 가야할 것이다. 그래야 정말 필요할 때 급유할 기회를 사용할 수 있다. 즉, 정말 필요할 때만 급유를 하는 식으로 해야할 것이다.
그래서 dfs를 이용하되 parameter로 연료통에 남아있는 연료량도 넘겨주면서... 근데 거리가 실수로 나오기 때문에 급유없이 가면서 남아있는 연료량을 계산할 때 실수로 인한 오차는 어떻게 처리할까?..도 문제였다.

일단 그냥 코드를 짜서 제출해 봤는데 AC를 받긴했다. 그리고 다른 사람들 코드랑, 공식 답안을 봤는데 나처럼 k번의 급유를 언제 할 것인지를 크게 신경쓰지 않은 것 같았다.
그래서 생각해보니... 아...

모든 비행장끼리는 다 직선거리로 이동이 가능하고, 모든 경우를 다 보는데 어떤 지점까지 갈 때, 연료가 남아서 어떤 지점까지 여러 군데를 거치며 급유없이 간다고 했을 때, 내 원래 생각은 급유없이 가니까 사용되는 연료를 빼주면서 (최대한 급유없이 오래 갈 수 있도록) 가는 것을 코딩하려 했는데... 그럴 필요가 없다. 여러 군데를 거쳐 어떤 지점까지 갈 필요 없이 그냥 바로 그 어떤 지점으로 가면 되기 때문이다! 그리고 바로 가는 것이 직선거리가 되어 연료도 더 조금 들 수 밖에 없다!!!

결국 k번의 급유 기회를 언제 어떻게 사용할지 신경 안써도 된다. 모든 경우를 다 보기 때문에 각각의 경우마다 급유를 하는 것으로 처리해도 된다!

이것이 이 문제의 핵심이 아닐까 생각한다.
아, 그리고 나는 dfs로 코드를 짰는데, 그러면 어떤 지점까지 다른 지점들을 거쳐 돌아가는 경우를 먼저 탐색하게 될 경우 그 지점까지 바로 가는 경우를 못 보게 된다.

그래서 공식 코드에서도 bfs를 사용하는 것 같다.

결론
1. 돌아가는 것보다 바로 가는 것이 항상 더 낫기 때문에 매번 급유를 받는 것으로 해도 상관없다. k번의 급유 기회를 언제 사용할지 신경쓰지 않아도 된다!
2. dfs를 이용하면 더 나은 경우를 못보게 될 수 있으므로 bfs를 사용해야 한다.

그리고 각 지점간의 거리를 double형으로 만들어서(sqrt) 연료량과 비교하는 대신 그냥 int형으로 제곱에 해당되는 값끼리 비교하면 시간이 좀 덜 걸린다. 그리고 int형으로 해도 상관없는 것이 k번의 급유 기회를 언제 사용할지 신경쓰지 않아도 되기 때문이다. 만약 남은 연료량을 계산해야 했다면 int형으로 하기 힘들 것 같다.(물론 double형이라도 오차를 어떻게 처리할 것인가도 문제겠고...)
좋은 문제같다.