접근방법
- 벽을 부수고 나아가는 정점을 토대로 진행 하게 된 경우,
벽을 부쉈다는 토글에 의해서 방문 처리 되어서 여러 가지 조건에 의해서
벽을 부수지 않았는데도 종착지에 도착할 수 있는데,
이미 방문 처리 되어서 종착지에 도달 못하는 경우가 발생할 수 있다!
라는 점을 생각해야 한다.
: 문제를 읽어보고, 생각해야 한다.
모든 경우에 대해서 생각해보자.
0000
1110
0000
0111
0110
0000
과 같은 경우는 어떻게 될까?
-> 빙돌아서 가는 경우가 최단경로일때는 15이고, 그런데,
32의 벽을 뚫고 가는 경우도 있다. 이때는 9이다.
- 최단거리가 달라져서 최초값이 최단거리가 아닐 수 있다.
반례가 생각나지 않을 수 있지만,
이 때 진행하는 방법은 기존의 visited 사용하는 것과 추가적으로
벽을 한 번 부쉈을 때 기록하는 visited 으로 나누어서 진행하면 된다고 한다.
-
경주로 문제가 비슷한 문제라고 한다.
-
벽 부수고 이동과 동일한 방법으로 했는데 계속 틀린다. ㅋㅋ
250123 - 틀림.
- 잘못된 생각.
1번.
벽을 부쉈다는 유무를 큐에다가 넣고 탐색하는 방식을 생각했는데
잘못된 생각이다. 지금 이렇게 하게 되면,
만약에 0번 인덱스에서 걸렸다고 한다면 나머지 1,2,3번의 cur는 벽을 부쉈다는 건데 탐색이 불가하다.
- 그렇다면 이렇게 할 경우에도 문제다.
2번.
누적되지 않는다. : 조건 처리 식에 해당되지 않음.
-> 문제를 풀기 전에 구상을 해보고, 잘못된 접근이라는 것을 판단해야 한다.
: 만약 0,1의 벽을 부수고 진행하고 있다. 그런데 다음 정점에 누적되어야 한다.
1번으로 하면 현재 정점에 대한 나머지 4번의 경우 문제가 되고,
2번으로 하더라도
- 어찌저찌 풀었다. 그런데 15퍼센트 에서 틀림.
https://www.acmicpc.net/submit/2206/89052641
생각할 부분.
- 최단거리로 가는게 아니라, 빙 돌아서 종착점까지 가는 부분이 전부다 0이라고 할 경우 에 대해서 생각해야 한다.
반례
6 5
00000
11110
00000
01111
01111
00010
- 나의 코드로 출력하면 -1이 나온다. 하지만, 종착지 까지 갈수 있는 경로가 있다.
-> 즉 벽이 있어서 못가는 영역이 있더라도 만약에 0밖에 없어서 빙 돌아서 갈수 있다는 거를 생각하게 되면, 나의 코드처럼. 방문체크를 먼저 처리하면 안된다.
큐에 넣을 수가 없다. 왜냐하면 최단거리로 가다가 이미 방문처리를 해버렸기 때문에 뱀처럼 돌아갈수 없는 구조의 코드이다.
최단거리를 구하는 거다.
- 벽이 존재하지 않을 때의 최단거리,
- 벽이 존재할 때의 최단거리로 분류해서 진행하자.
🔥🔥🔥