힌트별로 정리했습니다. 막히실 때마다 조금씩 공개해서 보세요!
Hint 1. 문제에서 주어지는 출발점과 도착점을 포함한 모든 지점들을 '하나의 정점' 으로 생각해 보겠습니다. 그렇게 한다면, 출발점에서 시작해 여러 정점을 지나 도착점으로 도달할 수 있다면 이동에 성공하게 된다고 할 수 있을 것입니다.
Hint 2. 이제 이 정점 사이를 이동할 수 있는지를 판단해야 합니다. 문제에는 '착륙 허용 최대횟수' 와 '연료통 크기' 라는 것이 있습니다. 이 두 조건은 정점 사이를 이동할 수 있을지의 여부를 판단하게 될 것입니다.
Hint 3. '착륙 허용 최대횟수' 는 정점의 이동 횟수를 제한합니다. 즉 시작점에서 출발해 도착점으로 가기 위해서는 지나갈 수 있는 정점의 개수가 제한되어 있습니다. '연료통 크기' 는 한 번에 이동할 수 있는 거리를 제한합니다. 즉 정점과 정점 사이를 지나갈 수 있는가의 여부는 연료통의 크기에 따라 좌우됩니다. 연료통의 크기가 너무 작아 이동할 수 있는 거리가 정점 간의 거리보다 짧다면 이동할 수 없겠지요.
Hint 4. 위의 힌트를 종합하면 이 문제는 두 제한조건에 따라 정점 간의 이동이 가능한지를 판단해야 하는 문제가 됩니다. 따라서 BFS같은 그래프 탐색 알고리즘을 이용해 문제를 해결할 수 있습니다. 무식하게 해결 방법을 생각한다면, 착륙 허용 최대횟수는 고정되어 있으므로 값이 변할 수 있는 연료통 크기의 값을 가장 작은 값부터 가장 큰 값까지 모두 대입하여 BFS를 돌려보는 것입니다.
Hint 5. Hint 4의 방법대로 한다면 답을 구할 수 있지만, 너무 많은 경우를 시도해 봐야 하므로 시간 초과를 받기 쉽습니다. 여기서 더 최적화할 수 있는 방법이 있습니다. 이 문제에서는 연료통의 크기가 작을 수록 불리하고, 연료통의 크기가 클 수록 유리합니다. 그러므로 연료통의 크기의 값을 이분 탐색으로 결정, 즉 매개 변수 탐색을 이용하여 시도 횟수를 크게 줄일 수 있습니다.
따라서 매개 변수 탐색을 이용해 연료통의 크기의 값을 정해 보고, 해당 연료통의 크기마다 BFS를 실행해 보아 탐색이 가능한지를 판단해 답을 구하는 문제가 됩니다.
ksoosung77 2년 전
아무리 아이디어를 떠올려볼라해도 그에 반박되는 반례가 떠오르는 나머지 시작도 못하고 있습니다
어떻게 시작해야 하나요? 힌트좀 주시면 감사하겠습니다 😋