백준 2206 벽 부수고 이동하기

백준 2206 벽 부수고 이동하기

---

오늘 문제도 엄청 오래 걸렸다. 사실 처음에 풀이한 방식이 시간 문제에서 걸릴 가능성이 높단걸 알면서도 한번 해본게 문제였던 것 같다.

똑같은 DFS 문제인데, 이번에는 벽을 딱 한 번 뚫을 수 있다는 차이가 있었다.
그래서 가장 처음 한 풀이는, 모든 벽 중 한개씩 뚫린 맵들에 대해 각각 DFS 를 굴려서 최솟값을 찾는 방안이었다.
값은 잘 나오나 시간 초과가 나왔다.

그래서 변경한 방법은 큐에 기존에 x,y 좌표를 갖는 Pair 를 담았다면, 이번에는
벽을 한번 뚫었는지의 여부를 함께 담에서 큐를 돌렸다는 것이었다.
또 visited 배열도 3차원으로 만들어 해당 위치까지의 최솟값을 벽을 한번 뚫고 온 경우와 아니었을 경우에 대해 각각 저장해 주었다.

        while (!q.isEmpty()) {
            Pair cur = q.poll();

            if (cur.x == n-1 && cur.y == m-1) {
                System.out.println(cur.cnt);
                return;
            }

            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.x + dir_x.get(dir);
                int ny = cur.y + dir_y.get(dir);

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                int nxt_cnt = cur.cnt+1;

                if (table[nx][ny] == '0'){
                    if (!cur.chance && !visited[nx][ny][0]) {
                        q.add(new Pair(nx,ny, false, nxt_cnt));
                        visited[nx][ny][0] = true;
                    } else if (cur.chance && !visited[nx][ny][1]) {
                        q.add(new Pair(nx,ny, true, nxt_cnt));
                        visited[nx][ny][1] = true;
                    }
                } else if (table[nx][ny] == '1') {
                    if (!cur.chance) {
                        q.add(new Pair(nx,ny, true, nxt_cnt));
                        visited[nx][ny][1] = true;
                    }
                }
            }
        }

핵심이 되는 DFS 부분은 다음과 같다. 메모리 초과가 계속 나와서 배열을 전부 숫자에서 캐릭터로 바꿔주었고, 기존에 int로 하던 chance 처리도 boolean으로 바꾸어 주었다.
(사실 문제는 사소한 실수였다.)