백준 2206 벽 부수고 이동하기

일단 나는 벽을 부수지 않은 경우, 부순 경우를 각각 배열로 선언하고, 큐에도 (행, 열, 부순 여부) 를 넣어서 bfs를 돌렸다.

하지만 AC를 받은 후 내 코드 보다 훨씬 빠른 namnamseo님의 코드를 봤는데, 훨씬 간단하고 기발한 방법인 것 같아 여기 기록해둔다.

bfs를 두 번 돌리는데, 한 번은 시작점(1, 1)에서부터, 또 한 번은 끝점(n, m)에서부터 돌린다.
그렇게 돌려서 d1배열에는 시작점으로부터 각 점까지의 최단 거리, d2배열에는 끝점부터 각 점까지의 최단 거리를 구한는데, 이 때 벽을 만나게 되면 더 이상의 bfs는 하지 않기 때문에 벽을 만난 경우 벽 1개까지의 최단 거리를 구하게 된다.

그리고 나서 각 점까지의 최단 거리를 합쳐서 그 중 최소를 구하게 되면 최대 벽 1개를 부술 수 있을 때의 최단 거리가 구해진다!!

만약 벽이 여러개 있어서 경로가 없는 경우에는 처음 d1, d2배열을 큰 수로 초기화 해주는데, 적어도 d1, d2중 하나에는 큰 수가 갱신되지 않고 그대로 있게된다. 그래서 최종적으로 구한 값이 n * m보다 크면 -1을 출력해준다.