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

📄 링크

벽 부수고 이동하기

---

💡 문제 분석

(1, 1) 에서 (N, M)까지 최단경로를 찾는 문제입니다. 일반적인 BFS와 같지만 벽을 딱 한 번 부술 수 있다는 점이 다릅니다.
어떤 벽을 부숴야 최단 거리로 갈 수 있는지 모르기 때문에 그냥 다 부숴보기로 합니다.
dist[4][2][1] = (4, 2)에 벽을 한 번 부수고 도달했을 때 최단거리입니다, dist[4][2][0]이라면 벽을 안 부수고 도달했기 때문에 한 번의 기회가 남아 있다는 것을 알 수 있습니다

bfs를 돌면서 길이 있다면 그냥 가고 없다면, 벽을 부순 적이 없다면 부수고, 부순 적이 있다면 가지 못합니다.
그리고 따로 방문처리 배열을 만들지 않고, dist 배열이 갱신된 적이 있다면 그냥 넘어가도록 합니다

---

⌨️ 코드

public class Boj2206_tk {

    static class Check {
        int y, x, check;

        Check(int y, int x, int check) {
            this.y = y;
            this.x = x;
            this.check = check;
        }
    }
    static int N, M;
    static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
    static char[][] map;
    static int[][][] dist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new char[N][M];
        dist = new int[N][M][2];
        for(int i = 0; i < N; i++)
            map[i] = sc.next().toCharArray();
        System.out.println(bfs(new Check(0, 0, 0)));
    }

    public static int bfs(Check start) {
        Queue<Check> q = new LinkedList<>();
        q.add(start);
        dist[start.y][start.x][start.check] = 1;
        while(!q.isEmpty()) {
            Check cur = q.poll();
            if(cur.y == N - 1 && cur.x == M - 1)
                return dist[cur.y][cur.x][cur.check];
            for(int d = 0; d < 4; d++) {
                int ny = cur.y + dy[d];
                int nx = cur.x + dx[d];
                if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                if(dist[ny][nx][cur.check] != 0) continue;
                if(map[ny][nx] == '0') {
                    dist[ny][nx][cur.check] = dist[cur.y][cur.x][cur.check] + 1;
                    q.add(new Check(ny, nx, cur.check));
                }
                else {
                    if(cur.check == 0) {
                        dist[ny][nx][1] = dist[cur.y][cur.x][cur.check] + 1;
                        q.add(new Check(ny, nx, 1));
                    }
                }
            }
        }
        return -1;
    }
}

---

📋 결과