[JAVA] 백준 2206 - 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

전형적인 BFS문제처럼 보이지만 벽을 하나 부술 수 있는 문제라서 상당히 복잡했다.

핵심 개념을 떠올리기가 힘들어서 일단 바이러스 문제처럼 브루트포스식으로 해봤는데 시간이 어림도 없었다.

결국 핵심 개념은 특정 좌표 (X,Y)까지 도착했을 때 벽을 부쉈는지 안 부쉈는지의 상태를 저장할 수 있어야하고, 그에 따라 경로도 완전히 달라지기 때문에 별도로 관리되어야 한다는 점이다.

그래서 방문체크배열을 3차원으로 추가해 [x][y][벽부쉈는지] 형식으로 작성하고 BFS를 돌리다가 벽을 만나면 부수고 부순쪽의 방문체크를 하고 길을 만난 경우에는 부수지 않는 쪽의 방문체크를 하면서 목적지인 (N,M)에 도달해서 최단경로가 산출됐는지를 체크했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int h = a[0];
        int w = a[1];
        int[][] map = new int[h][w];
        for (int i = 0; i < h; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }
        int[] dx = {1, -1, 0,0};
        int[] dy = {0,0,1,-1};
        boolean[][][] visited = new boolean[map.length][map[0].length][2];
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(0, 0, 1,0));
        visited[0][0][0] = true;
        int len = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            Position cur = q.poll();
            int ch = cur.h;
            int cw = cur.w;
            int depth = cur.depth;
            int cbr = cur.br;
            if (ch == map.length - 1 && cw == map[0].length - 1) {
                len = Math.min(len, depth);
            }
            for (int i = 0; i < 4; i++) {
                int ti = ch+dx[i];
                int tj = cw+dy[i];
                if(ti<0||ti>=map.length||tj<0||tj>=map[0].length) continue;
                if(map[ti][tj]==0&&!visited[ti][tj][cbr]){
                    visited[ti][tj][cbr] = true;
                    q.offer(new Position(ti,tj,depth+1,cbr));
                }
                if(map[ti][tj]==1&&cbr==0&&!visited[ti][tj][1]){
                    visited[ti][tj][1] = true;
                    q.offer(new Position(ti,tj,depth+1,1));
                }
            }
        }

        if(len==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(len);
    }


}

class Position {
    int h;
    int w;
    int depth;
    int br;

    Position(int h, int w, int d, int br) {
        this.h = h;
        this.w = w;
        this.depth = d;
        this.br = br;
    }
}

맨날 상하좌우 체크할때 파라미터 일일히 쓰기 힘들었는데

       int[] dx = {1, -1, 0, 0};
       int[] dy = {0, 0, 1, -1};

이렇게 쓰는 습관을 들이면 속도가 좀더 빨라질 것 같다.