BOJ 2589 - 보물섬 (https://icpc.me/2589)
그렇게 어렵지는 않은 문제인데, bfs를 어떻게 돌리냐에 따라 소요시간이 제법 차이난다.
처음 제출했을 때는 332ms 나왔는데, 이후 몇 번 고쳐서 196ms까지 줄였다. (자바 기준으로는 맞은 사람들 중에 빠른편인듯)
아주 간단하게 시간 줄이는 법을 적어보려고 한다.
시간 줄이는 방법
이동 가능한 구역마다 각각을 시작점으로 하는 bfs를 돌린 뒤에, 가장 오래 걸리는 최단거리를 구해서 갱신해주면 되는 것이 기본적인 방법이다.
그런데 잘 생각해보면 가장 오래 걸리는 최단거리를 구할 수 있는 시작점은 다음과 같다.
- 현재 상태에서 움직일 수 있는 칸이 1개인 지점
- 현재 상태에서 움직일 수 있는 칸이 2개인데 구석에 있는 지점
- 위아래 중 이동할 수 있는 칸이 1개, 좌우측 중 이동할 수 있는 칸이 1개면 구석으로 간주할 수 있음
이 것을 제외한 지점에서는 bfs를 돌리더라도 가장 오래 걸리는 최단거리를 구할 수 없기 때문에 제외해도 된다.
그래서 현재 지점 기준으로 위의 기준을 만족한 경우에만 bfs를 돌리도록 구현했다.
고수 분들은 더 최적화 하실 수 있겠지만, 이 정도만 해줘도 충분히 시간이 빨라지는 것을 볼 수 있었다.