백준 2206 벽 부수고 이동하기 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/2206

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int[][] map;
    static boolean[][][] visited; //세번째칸은 0, 1이고 각각 벽을 뚫기전인지 뚫은 후인지를 나타냄
    static int R, C;
    static int[] dr = {-1, 1, 0, 0}; //상하좌우
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //벽을 한 개 까지 부수고 이동하여도 된다.
        //한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
        //맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());

        map = new int[R][C];

        for(int r = 0 ; r < R ; r++) {
            String[] arr = br.readLine().split("");
            for(int c = 0 ; c < C ; c++) {

                int tmp = Integer.parseInt(arr[c]);
                map[r][c] = tmp;

            }
        }

        visited = new boolean[R][C][2];

        //여기까지 초깃값
        int answer = BFS();
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();



    }
    static int BFS() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1, false));

        while(!q.isEmpty()) {
            Node curNode = q.poll();
            int curR = curNode.r;
            int curC = curNode.c;
            int curCnt = curNode.cnt;
            boolean curBreak = curNode.isBreak;

            if(curR == R-1 && curC == C-1) return curNode.cnt;




            for(int i = 0 ; i < 4 ; i++) {
                int nextR = curR + dr[i];
                int nextC = curC + dc[i];

                if(!isValid(nextR, nextC)) continue;

                if(map[nextR][nextC] == 0) { //벽이 아니고
                    if(curBreak && !visited[nextR][nextC][1]) { //이전에 1회 뚫기 사용 한채로 해당 타일 지나지 않았다면
                        q.add(new Node(nextR, nextC, curCnt+1, true)); //1회뚫기 사용한채로 큐에 넣고 방문체크
                        visited[nextR][nextC][1] = true;
                    }
                    else if(!curBreak && !visited[nextR][nextC][0]){ //1회 뚫기 사용 안했고 사용 안한채로 해당 타일 지나지 않았다면
                        q.add(new Node(nextR, nextC, curCnt+1, false)); //1회뚫기 사용 안한채로 큐에 넣고 방문체크
                        visited[nextR][nextC][0] = true;
                    }

                }
                else if(map[nextR][nextC] == 1){ //벽에 마주쳤다면
                    if(!curBreak && !visited[nextR][nextC][1]) { //1회 뚫기 사용안했고 해당 타일을 방문하지 않았을때만
                        q.add(new Node(nextR, nextC, curCnt+1, true));
                        //여기부터는 1회뚫기 사용했기때문에 로직상, 앞으로 계속해서 사용한채로(isBreak = true 인 채로) 큐에 추가될 예정
                        //한번 true로 바뀌면, 위의 if(!curBreak) 로직은 다시 작동할 수 없음. (다시는 벽 뚫을 수 없음)
                        visited[nextR][nextC][1] = true;
                    }
                }

            }
        }

        return -1; // 끝까지안나오면 못가는거고
    }

    static class Node {
        int r, c, cnt;
        boolean isBreak;

        public Node(int r, int c, int cnt, boolean isBreak) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.isBreak = isBreak;
        }
    }
    
    static boolean isValid(int r, int c) {
        if(r < 0 || r >= R || c < 0 || c >= C) return false;
        return true;
    }

}

일반 BFS와 달랐다.

우리가 흔히 아는 map이 주어진다.
ex)
000
011
000 이런식으로.
0은 통과가능, 1은 벽이다
1행1열부터 주어진 값 R행 C열까지의 최단거리를 구하는데,
벽을 한번 부술 수 있다.

오답

처음엔, 어.. 벽이 주어진 위치(map[][] == 1인곳)를
List(List walls)에 기록해놓은 다음에,
해당 List를 순회(벽의 위치를 순회하며)하며
벽이 있는곳을 (map값이 1인곳을) 부셔주며 (map값을 0으로 바꿔주며)
각각 최단거리를 구하는 BFS를 돌려줬다.

BFS 개념은 알거라고 생각하고 생략하고,
벽을 부수고 BFS를 돌리는 오답코드는 다음과 같다.

for(int[] wall : walls) {
            map[wall[0]][wall[1]] = 0;
            visited = new boolean[R][C];
            int cur = BFS();
            if(cur != -1 && cur < answer) answer = cur;
            map[wall[0]][wall[1]] = 1;
        }

당연히 BFS를 벽의 횟수 + 1(맨 처음 상태) 를 해주니까
메모리 초과가 나왔다.

분명히 문제 처음에 풀때 감이 오긴 왔다.
BFS 여러번 돌려주면 이거 시간이나 메모리나 초과가 나긴 하겠네.. 라고
근데 응용된 부분(벽 부수기)를 현명하게 대처할 생각을 못했기에 그렇게 풀었다.

하지만, 하나씩 벽을 부수며 BFS를 돌리지 않고도,
내가 벽 부수기를 사용하고 왔는지 여부 (Node 클래스의 isBreak)를 사용하여
한번의 BFS로 구할 수 있다.
해당 내용이 맨 위의 풀이이다.

코드를 읽기 전에, 이해해야할 내용은,
visited[r][c][0] 은 아직 벽 부수기 1회 사용을 사용하지 않은 상태로
r행 c열을 방문했는지 여부의 배열이고 (앞으로 벽 부수기를 사용할 수 있다),

visited[r][c][1] 은 벽 부수기 1회 사용을 사용해버린 상태로
r행 c열을 방문했는지 여부의 배열이다 (더이상 벽을 부술 수 없다).

Node의 isBreak필드도 마찬가지이다.

주석의 코드를 잘 읽도록 하자.

ps

참고 : https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-JAVA%EC%9E%90%EB%B0%94

이 문제 약간 1회 벽 부수기 뿐 아니라 여러번 벽 부수기로 응용 가능 할 것 같다.
하지만 그때는 isBreak필드를 true false가 아니라, int형으로 해주고

벽을 뚫을때마다 isBreak + 1,
방문배열을 몇번까지 부술수 있는지에 따라 다르게 만들어야 할 것 같다.
근데 이렇게 만들면 메모리가 버틸 수 있으려나..?