BOJ 14619 - 섬 여행
한창 PS 공부하던 시절, 이 문제를 풀기 위해 하루종일 제출을 시도했던 기억이 있다.
작년 8월이었는데.. 결국 시간 초과 + 틀렸습니다 콤보를 맞고 풀지 못했었다.
지금 와서 생각해보면 딱히 못풀만한 난이도는 아니었고 내 역량 부족이었다고 생각했는데, 간만에 기억나서 풀어보니 맞았다.
문제를 풀기 위한 기본 알고리즘을 잘 알고 있는 것도 중요하지만, 문제 내용을 읽었을 때 어디까지 최적화할 수 있는지 고민해보는게 매우 중요한 것 같다.
처음 이 문제에 도전했을 때는 느슨하게 DFS를 짜고 거기에 적당히 몇 가지 상황을 커트해주면 될 거라고 생각했었는데, 가만 생각해보니 너무 안일한 마인드였다.
왜냐면 이 문제에는 다음과 같은 특성이 있기 때문이다.
- 어떤 상황 및 조건을 만족 했을 때의 최소값을 구하라고 했음
- 그런데 그 최소값을 구하기 위한 데이터가 쿼리를 처리하는 도중에 변경되지 않음
- 단순히 모든 케이스를 탐색하기에는 중복이 많이 발생함 (한번 방문한 곳을 다시 방문 가능하기 때문에)
그러므로 이 문제는 DP로 접근하는 것이 맞고, 그렇게해서 풀 수 있었다.
접근 방법
A번 섬에서 정확히 K번 이동하였을 때 도착 가능한 섬들의 높이 중 가장 낮은 섬의 높이 를 구하라는 문장에서 다음과 같은 식을 생각해낼 수 있다.
DP[A][K] = min(DP[A][K], dfs(A와 연결되는 지역, K-1))
A랑 B가 연결되어있고, B랑 C가 연결되어 있는데 A에서 두번 이동해서 도착 가능한 섬 중에 가장 낮은 섬이 C였다고 치자.
(각각의 높이는 3,2,1)
그렇다면 이 상황에서는, B에서 한번 이동해서 도착 가능한 섬 중에 가장 낮은 섬도 C이다.
이런 내용들을 DP 배열에 기록해두면 나중에 다른 쿼리가 들어오거나 하면서 중복 이동이 발생해도 DP 배열의 값을 반환하면 되기 때문에 굳이 같은 케이스를 반복할 필요가 없어진다.
이제 남은 문제가 있다면 예외 처리인데, 인풋 중에서 시작 섬이랑 연결된 다리가 한 개도 없는 경우 가 존재할 수 있다.
이 경우는 그냥 시작 섬에 연결되는 노드가 있는지 확인하고, 없으면 -1 출력할 수 있도록 잘 처리해주면 된다.
최소값 구하는 문제이기 때문에 DP 배열은 미리 큰 값으로 초기화 해놓을 것을 권장.