벽 부수고 이동하기

문제

2206번: 벽 부수고 이동하기

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

제한 사항

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

입출력 예

입력	출력
6 4
0100
1110
1000
0000
0111
0000	15
4 4
0111
1111
1111
1110	-1

입출력 예 설명

아이디어

bfs

벽을 부쉈는지 안 부쉈는지 보려고 visited를 3차원 배열로 바꿈

1 X 1 사이즈일 때는 탐색 안 하더라도 무조건 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 three2206 {
    private int[] drow = new int[] {0, 0, 1, -1};
    private int[] dcol = new int[] {1, -1, 0, 0};
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int colNum = Integer.parseInt(infoToken.nextToken());
        int rowNum = Integer.parseInt(infoToken.nextToken());
        int[][] map = new int[colNum][rowNum];

        for (int i = 0; i < colNum; i++) {
            String[] mapInfo = reader.readLine().split("");
            for (int j = 0; j < rowNum; j++) {
                map[i][j] = Integer.parseInt(mapInfo[j]);
            }
        }

        Queue<int[]> toVisit = new LinkedList<>();
        toVisit.add(new int[] {0, 0, 0});
        boolean[][][] visited = new boolean[2][colNum][rowNum];
        int[][] dist = new int[colNum][rowNum];

        while(!toVisit.isEmpty()) {
            int[] current = toVisit.poll();
            for (int i = 0; i < 4; i++) {
                int nextRow = current[1] + drow[i];
                int nextCol = current[0] + dcol[i];

                if (nextCol < 0 || nextCol >= colNum || nextRow < 0 || nextRow >= rowNum)
                    continue;

                // 다음 칸에 벽이 있을 때
                if(map[nextCol][nextRow] == 1) {
                    // 벽을 부순 적이 있는지, 벽을 방문한 적이 있는지
                    if (current[2] == 0 && !visited[1][nextCol][nextRow]) {
                        visited[current[2]][nextCol][nextRow] = true;
                        dist[nextCol][nextRow] = dist[current[0]][current[1]] + 1;
                        toVisit.offer(new int[] {nextCol, nextRow, 1});
                    }
                }
                // 벽이 아닐 경우
                // 벽을 부순 여부에 따라 방문을 했는지 체크
                else {
                    if (!visited[current[2]][nextCol][nextRow]) {
                        visited[current[2]][nextCol][nextRow] = true;
                        dist[nextCol][nextRow] = dist[current[0]][current[1]] + 1;
                        toVisit.offer(new int[] {nextCol, nextRow, current[2]});
                    }
                }
                if (nextCol == colNum - 1 && nextRow == rowNum - 1) {
                    System.out.println(dist[nextCol][nextRow] + 1);
                    System.exit(0);
                }
            }
        }
        if (colNum == 1 && rowNum == 1) System.out.println(1);
        else System.out.println(-1);
    }

    public static void main(String[] args) throws IOException {
        new three2206().solution();
    }
}