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

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

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

풀이

최단거리 문제이므로 BFS를 사용했다. 처음에는 boolean타입의 flag를 사용하여 벽을 부쉈는지 여부를 확인하였는데 이렇게 되면 벽을 부수지 않고 이동했을 때와 벽을 부수고 이동했을 때의 경로가 겹치게 되고, 최단거리더라도 더 이상 진행하지 못하게 되었다.

 

그래서 visited배열의 인덱스를 추가해서 벽을 부수지 않고 이동했을때의 방문 여부, 벽을 부수고 이동했을 때의 방문여부를 따로 담아 주었다. 그렇게 해도 괜찮은 이유는 아래와 같다. 

 

결국 최단거리는 둘 중 하나가 된다.

1. 벽을 부수지 않고 목적지 까지 도달할 수 있을 때의 최단거리
2. 벽을 하나 부수고 목적지 까지 도달할 수 있을 때의 최단거리

그러므로 visited배열의 인덱스를 추가해서 벽을 부수지 않고 이동했을 때의 방문여부, 벽을 부수고 이동했을 때의 방문여부를 따로 기록하고 먼저 목적지에 도달한 루트가 최단거리가 된다. 

 

코드

import java.util.*;
 
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) {
        Scanner scanner = new Scanner(System.in);
 
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();
        
        board = new int[n][m];
        for (int i = 0; i < n ; i++) {
            String str = scanner.nextLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.valueOf(str.charAt(j)) - '0';
            }
        }
 
        visited = new boolean[n][m][2];
        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; //0은 벽을 부시지 않고 방문한 노드의 방문 여부
        visited[x][y][1] = true; //1은 벽을 부시면서 방문한 노드의 방문 여부
 
        while (!q.isEmpty()) {
            Node current = q.poll();
 
            if (current.x == n - 1 && current.y == m - 1) return current.count;
 
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
 
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if(board[nx][ny] == 0) { //벽이 아닐 때
                        if (visited[nx][ny][current.wall] == false) { //현재까지 온 방법(벽을 부쉈는지 아닌지)으로 방문한 적이 없다면 방문한다.
                            q.add(new Node(nx, ny, current.count + 1, current.wall));
                            visited[nx][ny][current.wall] = true;
                        }
                    }    
                    else if (board[nx][ny] == 1) { //벽일때
                        if (current.wall == 0 && visited[nx][ny][1] == false) { //현재까지 벽을 부순적이 없고, 벽을 부숴서 방문한 적이 없다면 방문한다.
                            q.add(new Node(nx, ny, current.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; //벽을 부시면서 왔는지 아닌지. 0이면 아니고 1이면 벽을 부시면서 왔다는 것을 의미한다.
 
        public Node(int x, int y, int count, int wall) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.wall = wall;
        }
    }
}