결국 방문배열이란 것은, bfs에서 '모든 경우'를 살펴보며 진행할 때, 같은 행위를 두번하면 비효율적이니 그걸 막기 위해 사용합니다.
따라서 방문배열은 '모든 경우'를 나타낼 수 있어야 합니다. 일반적인 bfs 문제에서 모든 경우는 결국 '이 위치에 이미 왔었다' 입니다.
따라서 그냥 2차원 방문배열로 나타내면 되는거구요.
이 문제에서 모든 경우는 말로 설명하자면 '해당 위치에 벽을 부순 상태로 이미 왔었거나, 해당 위치에 아직 벽을 부수지 않은 상태로 이미 왔었다.' 정도가 되겠습니다.
따라서 이걸 표현하기 위해 3차원 배열로 나타낸거구요.
이런식으로 모든 경우를 나타낼 수 있는 방문배열을 만들지 않을 경우 다음과 같은 문제가 발생합니다.
----------
000000 111110 010000 010111 010011 011011 000*10
실제 구현된 동작은 다를 수 있으나, 그냥 머리로만 한번 같이 생각해보죠.
1,1 지점에서 아래쪽으로 벽을 뚫고 진행한 녀석은 *까지 빠르게 갈꺼구요. *도 0이라고 칩시다.
어쨌든 *까지 도달했으니 *에도 방문배열에 체크를 했구요. 벽을 뚫고 진행했으니 목적지에는 도달할 수 없습니다.
그 와중에 1,1 지점에서 오른쪽으로 진행한 녀석은 꼬불꼬불한 길을 따라 천천히 * 직전까지 옵니다.
사실 얘는 *까지만 오면 벽을 아직 안부셨으니깐 목적지 좌측의 벽을 부수고 목적지에 갈 수 있습니다.
하지만 이미 방문체크가 되어있으니 * 지점에 갈수가 없어요 ㅠ
따라서 프로그램은 목적지에 도달하지 못한다고 판단할껍니다.
dpfkdvkr 2년 전 1
해결은 했으나 왜 이렇게 해결해야하는지 모르겠습니다 ㅠㅠ...
(하단의 코드는 어쩌다 맞아버린 코드입니다..!)
한 좌표에서 여러 방향으로 나아가면서, 8번 라인에 방문여부를 기록하는 부울형 배열에 방문정보가 이미 true라서 다시 못지나가는 오류때문에
3 6
010000
010111
000110
이 경우를 제대로 해결할 수 없었습니다.
왜 벽 부순후, 벽 부수기 전 방문여부를 따로 기록해야 하나요?