[BOJ] 2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

모든 벽에 대해, 그 벽을 부수고 DFS를 수행하는 방식으로 처리한다면 시간복잡도는 O(N^2M^2)으로 시간 내에 해결이 어렵습니다. 대신 아래와 같은 아이디어로 시간복잡도를 O(NM)으로 만들 수 있습니다. (참고로 저는 인덱스를 (0, 0) to (N-1, M-1)로 뒀습니다.)

최단거리는

i)  벽을 파괴하지 않고 (0, 0)에서 (N-1, M-1)까지 가는 거리이거나

ii) 임의의 벽에 대해, 그 벽과 인접한 4개의 칸 중에서 (0,0)과 가장 가까운 것의 거리 + 인접한 4개의 칸 중에서 (N-1,M-1)과 가장 가까운 것의 거리  + 1 중 하나입니다.

i)은 자명하게 O(NM)에 구할 수 있고 ii) 또한 미리 모든 방문 가능한 칸에 대해 (0, 0)과의 거리와 (N-1, M-1)과의 거리를 계산해두면 O(NM)에 구할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/2206.cpp