[BOJ] 14923 미로 탈출 (JAVA)

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

14923번: 미로 탈출

BFS 문제입니다.

visited 배열을 3차원으로 선언해서 지팡이를 사용하지 않았을 때, 사용했을 때를 나눠서 방문체크하면 쉽게 해결할 수 있습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
    public static void main(String[] args) throws Exception {

        int[] dr = { -1,  0,  1,  0 };
        int[] dc = {  0,  1,  0, -1 };
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        int[][][] visited = new int[2][N][M];
        st = new StringTokenizer(br.readLine(), " ");
        int sr = Integer.parseInt(st.nextToken()) - 1;
        int sc = Integer.parseInt(st.nextToken()) - 1;
        st = new StringTokenizer(br.readLine(), " ");
        int er = Integer.parseInt(st.nextToken()) - 1;
        int ec = Integer.parseInt(st.nextToken()) - 1;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } // end of input

        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(sr, sc, 1));
        visited[1][sr][sc] = 1;

        while(!q.isEmpty()) {

            Pos p = q.poll();

            if(p.row == er && p.col == ec) {

                System.out.print(visited[p.wand][p.row][p.col] - 1);
                return;

            }

            for (int dir = 0; dir < 4; dir++) {

                int nr = p.row + dr[dir];
                int nc = p.col + dc[dir];

                if(0 <= nr && nr < N && 0 <= nc && nc < M) {

                    if(map[nr][nc] == 0 && visited[p.wand][nr][nc] == 0) {

                        q.offer(new Pos(nr, nc, p.wand));
                        visited[p.wand][nr][nc] = visited[p.wand][p.row][p.col] + 1;

                    } else if(map[nr][nc] == 1 && p.wand == 1 && visited[0][nr][nc] == 0) {

                        q.offer(new Pos(nr, nc, 0));
                        visited[0][nr][nc] = visited[1][p.row][p.col] + 1;

                    }

                }

            }

        }

        System.out.print(-1);

    }

    static class Pos {

        int row, col, wand;

        public Pos(int row, int col, int wand) {

            this.row = row;
            this.col = col;
            this.wand = wand;

        }

    }

}