<baekjoon> 벽 부수고 이동하기

풀이

벽이 없는 '0'은 이동 가능하고 벽인 '1'은 이동이 불가능하다. 하지만 딱 한 번만 벽인 '1'을 부수고 목적지로 갈 수 있다.

이 문제를 dfs를 통해 풀면 시간초과가 날 수 있다. 그래서 BFS를 이용하여 문제를 해결하였다.

우선 현재위치에서의 이동 값이랑, 벽을 부쉈는지의 유무를 확인하기 위해 Point클래스를 만들었다. 그리고 가장 중요한 것은 3차원 방문 배열(boolean)을 만들어야한다. 벽을 부수고 이동한 방문 배열과 부수지 않고 이동한 방문 배열을 따로 두고 이동해야 한다. 그렇지 않으면 같은 좌표를 참조하게 되었을 때 방문하지 않은 좌표임에도 불구하고 이미 방문했다고 판단할 수 도 있기 때문이다.

 

4방 탐색을 통하여 한칸 씩 이동할 때마다 cnt를 +1 한상태로 Point형 객체에 저장한다. 4방 탐색을 하면서 벽을 부수지 않고는 이동이 불가능하면 벽을 뿌수는데 wall을 -1 해준다. 그다음부터는 벽을 뿌수는 것이 불가능하며 그래도 목표점에 도착하지 못하면 -1을 결과로 출력한다.(flag가 false일 경우)

도착했을 경우에는 Max값과 비교하여 이전 이동경로보다 더 짧으면 Max값을 변경한다.(flag 가 true인 경우).

 

코드