그래프와 순회. [2206]

[1. 문제 설명]

NxM 맵에서 [1, 1] 에서 [N,M] 으로 최단 경로를 출력하는데,

벽을 부수고 이동하는 것이 최소라면 벽을 최대 하나까지만 부수고 이동할 수 있다.

 

 

[2. 풀이 접근]

A. 잘못된 접근

1. 일반 bfs 접근 중, 이동하려는 벽이 막혀있으면, 일단 부시고, 백업 큐에 저장
   => 이미 부수고 온 경우라면, 이 위치에서는 더 이상 부수지 않고 스킵함.
2. 부수지 않고 이동해온 경우로 마지막 좌표에 도달 할 수 없는 경우,
   백업 큐에 저장한 것을 이용하여 bfs 를 수행

 

이 풀이가 틀린 이유는?

1. 벽을 부수지 않고 이동한 경우 도달 할 수는 있으나, 벽을 부수고 이동한 것이 최소 일 수 있기 때문

 

B. 올바른 접근

1. visits 테이블에 차원을 하나 추가
   => 벽을 부수고 이동한 경우와 그렇지 않은 경우
2. 벽이 막힌 경우 부수고 이동함
   => 이 때, 중요한 점은 visits 에 접근은 부수지 않은 경우와 비교하여 다른 index 로 하여 접근해야 함
   => 아래 그림과 같은 방식으로 접근한다고 보면 된다.
3. 벽을 부순경우와 부수지 않은 경우 중 먼저 도달 한 쪽을 이용하여 값을 반환

 

점선이 아직 부수지 않은 경우에 대한 테이블

실선이 부순 경우에 대한 테이블

 

이동하려는 곳이 막혀있고, 아직 부수지 않았다면, 

이 벽을 부숴 이동하는데, 이 때 바라봐야 할 테이블을 변경하도록 하는것이다.

 

 

 

[3. 코드]