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

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

---

📝 문제 설명

(1,1)에서 (N, M)까지 이동하는데 해당 칸이 1은 벽이 있어 이동할 수 없고 0인칸만 이동할 수 있다. 이때, 시작하는 칸과 끝나는 칸을 포함해서 최단거리를 구해야 한다.

이 문제에서 벽을 한번 깰 수 있는 기회가 있다. 벽을 깨서 기존의 거리 보다 최단 거리를 구할 수 있다면 1번 깰 수 있다.

✨ 제출 코드

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

public class Main {
    static int [][] graph;
    static int N;
    static int M;
    static boolean [][][]visited;

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

    public static class Node{
        int x;
        int y;
        int wallBroken;
        int distance;

        Node(int x, int y, int wallBroken, int distance){
            this.x = x;
            this.y = y;
            this.wallBroken = wallBroken;
            this.distance = distance;
        }
    }

    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());

        graph = new int [N][M];
        visited = new boolean [N][M][2];

        for(int i = 0; i < N; i++){
            String str = br.readLine();

            for(int j = 0; j < M; j++){
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        int answer = bfs(0,0);
        System.out.println(answer);

    }
    public static int bfs(int x, int y){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x,y,0,1)); // (0,0)에서 시작, 벽 안 부숨, 거리 1
        visited[x][y][0] = true;

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.x == N-1 && cur.y == M-1){
                return cur.distance;
            }

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

                if(nx>=0 && nx<N && ny>=0 && ny<M){
                // 벽이 아니고 방문하지 않았으면 이동
                    if(graph[nx][ny] == 0 && !visited[nx][ny][cur.wallBroken]){
                        visited[nx][ny][cur.wallBroken] = true;
                        q.offer(new Node(nx,ny,cur.wallBroken,cur.distance+1));
                    }else if(graph[nx][ny] == 1 && cur.wallBroken == 0 && !visited[nx][ny][1]){
                        // 벽이지만 아직 벽을 부순 적이 없으면 부수고 이동
                        visited[nx][ny][1] = true;
                        q.offer(new Node(nx,ny,1,cur.distance+1));
                    }
                }
            }
        }

        return -1;
    }
}

 

✌️ 코드 설명

이 문제 또한 최단 거리를 구하는 문제이기 때문에 bfs를 이용하여 풀었다. 먼저 Node클래스를 하나 만들어서 여기에는 x좌표, y좌표, 부순 벽의 개수, 거리를 관리했다.

main 메서드는 넘어가고 bfs메서드 부터 보겠다. 문제에서 (1,1)부터 (N, M)까지의 최단거리를 구한다고 나와있다. 2차원 배열 graph를 [N][M]으로 설정했기 때문에 (0,0)부터 (N-1, M-1)으로 생각하여 풀었다.

bfs(0,0)부터 시작해보자. Node클래스 타입의 큐를 만들어 먼저 (0,0,0,1)을 큐에 넣어준다. 문제에서 시작점의 거리도 세야 하기 때문에 거리에는 1을 넣어주었다. 그리고 방문했는 지를 파악하기 위해 3차원 배열 visited를 만들었다. visited배열에는 x좌표, y좌표, 부순 벽의 개수를 관리해 주었다. 아직 벽을 부수지 않았으니 visited [0][0][0]을 true로 바꿔준다.

 

 

• visited [x][y][0]: (x, y) 좌표에 벽을 부수지 않고 방문했는지 여부
• visited[x][y][1]: (x, y) 좌표에 벽을 한 번 부수고 방문했는지 여부

 

 

계속 bfs를 돌면서 현재의 좌표가 N-1, M-1일 때의 거리를 return 해줄 거다. 아니라면 for문을 돌면서 다음 좌표의 상하좌우 체크하고 좌표 범위도 체크해준다.

만약, 벽이 아니고 방문하지 않았으면 true로 바꿔주고 거리를 1 증가시켜 q에 넣어준다.

그리고 벽이지만 해당 벽을 부순 적이 없으면 벽을 부수고 이동한다. 이 또한, true로 바꿔주는데 벽을 부수고 방문했기 때문에 visited [x][y][1]를 true로 바꿔준다. 그리고 큐에 추가해 준다.

불가능할 때는 -1을 출력해야 하기 때문에 최종 반환은 -1을 해준다.