[BOJ - 백준] 14923 - 미로탈출, Java(자바)

문제

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

14923번: 미로 탈출

풀이

visited 배열을 3차원으로 만들어 bfs로 풀었다. 0은 벽을 부수기 전, 1은 벽을 부순 후를 나타낸다.

코드

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

class Move {
    int r, c, dir;
    
    Move(int r, int c, int dir) {
        this.r = r;
        this.c = c;
        this.dir = dir;
    }
}

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(in.readLine());
        int Hx = Integer.parseInt(st.nextToken()) - 1;
        int Hy = Integer.parseInt(st.nextToken()) - 1;
        st = new StringTokenizer(in.readLine());
        int Ex = Integer.parseInt(st.nextToken()) - 1;
        int Ey = Integer.parseInt(st.nextToken()) - 1;
        
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            for (int j = 0; j < M; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        int cnt = 0;
        boolean isPossible = false;
        int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[][][] visited = new boolean[N][M][2];
        Queue<Move> queue = new LinkedList<Move>();
        visited[Hx][Hy][0] = true;
        queue.offer(new Move(Hx, Hy, 0));
        outer:
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Move move = queue.poll();
                if (move.r == Ex && move.c == Ey) {
                    isPossible = true;
                    break outer;
                }
                for (int d = 0; d < delta.length; d++) {
                    int dr = move.r + delta[d][0];
                    int dc = move.c + delta[d][1];
                    if (dr < 0 || dc < 0 || dr >= N || dc >= M || (map[dr][dc] == 1 && move.dir == 1))
                        continue;
                        
                    if (!visited[dr][dc][move.dir]) {
                        visited[dr][dc][move.dir] = true;
                        queue.offer(new Move(dr, dc, map[dr][dc] == 1 ? 1 : move.dir));
                    }
                }
            }
            cnt++;
        }
        System.out.println(isPossible ? cnt : -1);
    }
}