오답 여부: o
편집 시간: 2022년 2월 24일 오후 2:29
코드
Algorithm/2206.py at main · Junroot/Algorithm
풀이
기본적으로 BFS로 풀면된다. 하지만 방문한 위치를 체크하는 방법에서 어려움을 겪었다.
잘못된 풀이1
처음에는 벽을 부수든 부수지않든 한 번 방문한 위치는 재방문하지 않도록 구현했다. 하지만 어떤 위치에 대해서 기존에는 벽을 부수고 갔지만, 같은 횟수로 이동해서 벽을 부수지 않고 갈 수 있는 방법이 있다면 큐에 담을 필요가 있었다.
잘못된 풀이2
잘못된 풀이1때문에 나는 큐에 담겨있는 것중 거리가 가장 짧고, 거리가 같다면 아직 벽을 부수지 않은 것을 먼저 꺼내서 처리하면 해결될 거라고 생각했다. 하지만 이 방법은 잘못됐다. 목적지까지 도착하기 전에 중간 위치 x가 있을 때, 이 x에 출발지로부터 벽을 부수고 오면 더 빨리 올 수 있다면 벽을 부수지 않은 경우는 처리하지 않게 된다. 이럴 경우 (출발지) → x지점에서 벽을 부수는 것보다 x지점 → 목적지에서 벽을 부수는게 더 이득인 경우는 고려하지 않기 때문에 오답이 되었다.
맞는 풀이
결국에는 벽을 부순 경우와 부수지 않은 경우를 나눠서 방문 기록을 체크 해야된다. visited를 3차원 배열로 만들어서 x, y, 벽을 부순 회수로 3차원 배열을 만들어 해결했다.