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

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

 

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

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

---

1.  아이디어

 

최단거리를 구하는 일반적인 BFS에서 벽을 부수고 이동할 수 있는 조건이 추가된 문제로 방문 체크를 고도화하면 해결할 수 있다.

---

2. 문제풀이

 

방문 체크는 3차원 boolean 타입 배열과 2차원 int 타입 배열 두 가지를 활용했다.

 

3차원 boolean 타입 배열은 [행][열][벽을 부순 횟수] 이렇게 기록을 하는 방문 체크로 같은 위치를 같은 벽을 부순 횟수로 방문했는지까지 체크를 한다. 다음 칸이 이동할 수 있는 칸이면 해당 칸을 벽을 부순 횟수까지 일치하게 방문한 적이 있는지 체크하고 없으면 방문을 한다. 다음 칸이 벽이면 현재 벽을 부순 적이 있는지 체크하고 벽을 부순 적이 없으면 벽을 부수고 방문 처리를 한다. 이때 벽을 부쉈으므로 노드에 벽을 부순 횟수를 늘려서 Queue에 넣고 방문 체크도 벽을 부순 횟수에 맞게 체크를 해준다.

 

2차원 int 타입 배열은 벽을 부순 횟수 자체를 값으로 넣어줬다. 최초에는 Integer.MAX_VALUE로 초기화해서 0으로 초기화되는 문제를 방지해줘야한다.(0으로 초기화는 벽을 부수지 않고 방문 체크한 경우이므로) 이후 다음 칸이 이동할 수 있는 칸이면 해당 칸이 방문한적이 있는지 체크하고 방문한 적이 없으면 방문 처리를 해줬다. 다음 칸이 벽이면 현재 벽을 부순적이 있는지 체크하고 벽을 부순적이 없으면 벽을 부수고 방문 처리를 한다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        int r;
        int c;
        int cntBrokenWall;

        public Node(int r, int c, int cntBrokenWall) {
            this.r = r;
            this.c = c;
            this.cntBrokenWall = cntBrokenWall;
        }
    }

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int dist = bfs(N, M, map);
        System.out.println(dist);
    }

    private static int bfs(int N, int M, char[][] map) {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0));

        boolean[][][] visited = new boolean[N][M][2];
        visited[0][0][0] = true;

        int dist = 1;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.poll();
                if (node.r == N - 1 && node.c == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = node.r + dr[dir];
                    int nc = node.c + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == '0') {
                        if (visited[nr][nc][node.cntBrokenWall]) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall));
                        visited[nr][nc][node.cntBrokenWall] = true;
                    } else {
                        if (node.cntBrokenWall == 1) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall + 1));
                        visited[nr][nc][node.cntBrokenWall + 1] = true;
                    }

                }
            }

            dist++;
        }

        return -1;
    }

}

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

public class Main {

    private static class Node {
        int r;
        int c;
        int cntBrokenWall;

        public Node(int r, int c, int cntBrokenWall) {
            this.r = r;
            this.c = c;
            this.cntBrokenWall = cntBrokenWall;
        }
    }

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int dist = bfs(N, M, map);
        System.out.println(dist);
    }

    private static int bfs(int N, int M, char[][] map) {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0));

        int[][] visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        visited[0][0] = 0;

        int dist = 1;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.poll();
                if (node.r == N - 1 && node.c == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = node.r + dr[dir];
                    int nc = node.c + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == '0') {
                        if (visited[nr][nc] <= node.cntBrokenWall) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall));
                        visited[nr][nc] = node.cntBrokenWall;
                    } else {
                        if (node.cntBrokenWall == 1) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall + 1));
                        visited[nr][nc] = node.cntBrokenWall + 1;
                    }

                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기

 

- 3차원 boolean 타입 방문 체크

- 2차원 int 타입 방문 체크