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

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

---

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

2206번: 벽 부수고 이동하기

 

접근

일반적인 bfs 방문체크에서 벽을 부수는 것을 옵션으로 추가해야하는 문제이다.

visted를 3차원 배열로 선언하여, x, y축과 벽을 부섰는지의 여부를 체크할 수 있도록 구현했다.

 

최초 방문체크를 할 때 벽을 아예 부수지 않는 탐색자와 벽을 한 번 부술 수 있는 탐색자로 나눈다.

visited[x][y][0] = true;
visited[x][y][1] = true;

벽에 도달했을 때 현재 탐색자가 벽을 부순 적이 없었고 벽을 부술 수 있는 탐색자가 방문을 한적이 없었다면 방문체크를 한다.

 

while (!q.isEmpty()) {
            Node pick = q.poll();
            // 목적지[n, m]에 도착시 count 출력하고 종료
            if (pick.x == n-1 && pick.y == m-1) return pick.count;

큐에서 하나 뽑았을 때 좌표가 목적지와 같다면 시간이 얼마나 걸렸는지 반환하고 종료한다.

큐에 값이 다 비었을 때까지 반환되는 값이 없으면 -1을 반환한다.

위와 같이 진행할 경우 더이상 큐에 좌표를 넣을 수 없으므로 방문할 수 있는 새로운 루트로 탐색자가 이동할 것이다.

최단거리로 이동할 경우

다음과 같은 케이스에서는 벽을 부수지 못하는 탐색자는 더이상의 탐색을 진행할 수 없다.

벽 한개만 부수고 최단거리로 목적지에 도착한다.

 

코드

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

public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int n, m;
    static int[][] board;
    static boolean[][][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = (int) str.charAt(j) - '0';
            }
        }

        visited = new boolean[n][m][2]; // 2는 벽 부섰는지(1) 안부섰는지(0) 체크 여부
        System.out.println(bfs(0, 0));
    }

    private static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y, 1, 0));
        visited[x][y][0] = true;
        visited[x][y][1] = true;

        while (!q.isEmpty()) {
            Node pick = q.poll();
            // 목적지[n, m]에 도착시 count 출력하고 종료
            if (pick.x == n-1 && pick.y == m-1) return pick.count;

            for(int i = 0; i < 4; i++) {
                int nx = pick.x + dx[i];
                int ny = pick.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if(board[nx][ny] ==0) { // 벽 아닌 곳일 때
                        if (!visited[nx][ny][pick.wall]) {
                            q.add(new Node(nx, ny, pick.count + 1, pick.wall));
                            visited[nx][ny][pick.wall] = true;
                        }
                    }

                    else { // 벽인경우
                        if (pick.wall == 0 && !visited[nx][ny][1]) {
                            // 현 위치를 벅 부수고 방문처리한 적이 없고 벽을 부술 수 있는 탐색자가 방문한 적이 없을 경우
                            q.add(new Node(nx, ny, pick.count + 1, 1));
                            visited[nx][ny][1] = true; // 벽을 부수고 방문체크
                        }
                    }
                }
            }
        }
        return -1;
    }


    private static class Node {
        private int x;
        private int y;
        private int count;
        private int wall;

        public Node(int x, int y, int count, int wall) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.wall = wall;
        }
    }
}