BOJ 3055 - 탈출 (https://www.acmicpc.net/problem/3055)
오랜만에 BFS나 하나 풀어볼까 하다가 발견한 문제다.
표면상으로 느껴지는 난이도에 비해 정답률이 낮아서 놀랬는데, 막상 달려들어보니 충분히 그럴만한 문제였다고 생각했다.
이 문제 같은 경우는 토마토나 벽 부수고 이동하기 문제 등을 충분히 풀어봤으면 비교적 쉽게 감을 잡을 수 있으나, 그렇지 않은 경우는 조금 어려울 수 있으니 해당 문제들도 접해보길 권하고 싶다.
접근법
이 문제는 장애물(돌)이 존재할 수 있으며, 매 시간마다 이동 불가능한 지역이 늘어나는 특성을 가지고 있다.
일반적인 미로탐색 BFS의 경우 방문 상태를 기록할 배열이 하나만 필요한 경우가 많은데, 이 문제는 두 개를 필요로 한다.
- 물의 움직임을 기록할 배열
- 고슴도치의 움직임을 기록할 배열
푸는 방법은 다양할 수 있겠으나 나같은 경우 아래와 같은 순서로 문제를 풀었다.
1) 입력받은 지도 기준으로 물이 존재하는 위치들을 큐에 삽입한다.
2) 1번에서 작업한 큐를 기반으로 bfs를 한번 돌려준다. 이렇게 하면 물이 이동할 수 있던 모든 칸에 ‘N번째 시간에 물이 도달했다’는 정보가 저장된다. (이 내용은 물의 움직임을 기록할 배열에 저장한다)
3) 고슴도치가 출발하는 위치를 큐에 삽입하고, 고슴도치의 움직임을 기록할 배열에 bfs를 돌려준다.
3번의 경우 다음에 움직일 경로가 아래 조건을 만족하면, 배열에 기록하고 큐에 삽입해주면서 진행하면 된다.
- 현재 위치의 이동 시간이 n이라고 했을 때, 다음에 움직일 경로에 물이 도달한 시간이 n+1보다 큰 경우
- 다음에 움직일 경로에 장애물이 없으며, 해당 위치에 기록된 이동 시간이 없음 OR n+1보다 큰 경우
이 과정을 마무리하게 되면 예제 입력 1 기준으로 아래와 같은 배열이 만들어진다.
// 물의 움직임
MAX 1 0
3 2 1
4 3 2
// 고슴도치의 움직임
3 MAX MAX
2 1 MAX
1 0 1
고슴도치가 비버의 굴로 이동할 수 있었다면, 비버의 굴 위치에 최적값이 기록되었을 것이다.
(물론 배열 초기 상태는 아주 큰 값으로 초기화해놓고 시작했어야함)
최적값이 기록된 경우 해당 값을 출력, 그렇지 않으면 KAKTUS 를 출력하면 된다.
느낀 점
내가 풀어서 제출한 코드가 최적의 시간을 보장하지는 않았다.
Arrays.fill을 쓴게 문제거나 아마 따로따로 BFS를 돌린게 크지 않나 싶은데, 다음에 한 번 더 풀어봐야겠다😀