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

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

문제

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

 

문제 분석

조건

N×M 크기의 맵이 있다. 0은 이동할 수 있는 곳이고, 1은 벽이 있는 곳이다.

`1, 1`위치에서 `N, M`위치까지 이동하는데, 최단 경로로 이동하려 한다. 이동 중 1개의 벽을 부수고 이동할 수 있을 때 최단 이동 횟수를 구하는 문제이다. 이동이 불가능할 경우 `-1`출력

풀이방법

기본적인 BFS를 활용한 최단경로 구하는 문제에서 벽을 1번 부술수있는부술수 있는 경우가 추가된 형태이다. 각 칸에 이동했을 때, 벽을 부술 수 있는 횟수를 포함하여 `visited`를 관리하면 되는 문제이다. `Queue`에 넣는 좌표값에도 벽을 부술수 있는 횟수를 관리하기 위해 `Node`를 정의하여 관리해 주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node {
    int r;
    int c;
    int boom;   // 부수기 가능 횟수
    int count;  // 이동 수

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

public class Main {
    static int N, M;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        // 지도 입력
        char[][] map = new char[N + 1][M + 1];
        for (int r = 1; r <= N; r++) {
            String line = br.readLine();
            for (int c = 1; c <= M; c++) {
                map[r][c] = line.charAt(c - 1);
            }
        }
        System.out.println(bfs(map));
    }

    private static int bfs(char[][] map) {
        // 벽 부수기 가능 횟수를 포함하여 3차원 배열로 방문 표시
        boolean[][][] visited = new boolean[N + 1][M + 1][2];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        visited[1][1][1] = true;
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(new Node(1, 1, 1, 1));
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (now.r == N && now.c == M) {
                // 목표좌표 도달
                return now.count;
            }
            for (int[] dir : dirs) {
                int nextR = now.r + dir[0];
                int nextC = now.c + dir[1];
                if (nextR == 0 || nextC == 0 || nextR > N || nextC > M) {
                    continue;
                }
                if (map[nextR][nextC] == '1') {// 벽이면
                    if (now.boom == 1 && !visited[nextR][nextC][0]) {// 부수기 가능
                        visited[nextR][nextC][0] = true;
                        queue.add(new Node(nextR, nextC, 0, now.count + 1));
                    }
                } else {
                    if (!visited[nextR][nextC][now.boom]) {
                        visited[nextR][nextC][now.boom] = true;
                        queue.add(new Node(nextR, nextC, now.boom, now.count + 1));
                    }
                }
            }
        }
        return -1;
    }
}