1103. 게임

1103번: 게임

---

게임판을 탐색하는 전형적인 동적 계획법 문제이다. 어떤 칸에서 시작하여 게임을 진행할 수 있는 최대 횟수는 정해져 있으며, 그러한 횟수가 변하지 않기 때문에 한번 계산한 결과를 계속해서 써먹을 수 있고, 그래야만 한다. 메모이제이션 없는 완전 탐색의 시간복잡도는 $O(4^{nm})$이다. 실제로는 구멍에 빠지는 등의 종료로 인해 더 작겠지만 전체적으로 보면 지수 꼴의 시간 복잡도를 갖는다.

 

단 여기서 사이클을 고려해야 한다. 예를 들어 이런 경우다.

2 2
11
11

이 예제의 정답은 -1이다. 서로 다른 두 칸 사이를 무한히 왕복할 수 있기 때문이다. 따라서 이미 방문한 칸을 체크할 필요가 있다.

 

여기서 다시 한 번 문제가 생긴다. 게임판의 어떤 칸은 서로 다른 두 경로에 의해 방문될 수 있다(적어도 그러한 가능성을 부정할 수 없다). 따라서 어느 한 칸에 대한 계산을 끝낼 때, 방문 체크를 해제해야 나중에 할 계산의 정확성을 담보할 수 있다.

 

# 그럼에도 불구하고 틀리는 이유

게임판을 나가는 것도 한 번의 게임 진행으로 센다. 구멍에 빠진 경우 더이상 게임을 진행할 수 없으므로, dp 배열에 0을 저장해야 한다.

---