[백준OJ] 1473번 미로 탈출 (Java)

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

1473번: 미로 탈출

---

풀이

일반적인 BFS문제에서 N행M열을 돌렸는지 안돌렸는지 체크를 해주는게 문제의 포인트가 된다.

따라서 비트 마스크를 이용하여 visited[돌린 행을 체크해주는 비트][돌린 열을 체크해주는 비트][x][y] = 최소 시간 을 이용하여 문제를 해결해주었습니다.

 

예를 들면 4x4 행렬이 있고, (0,1) 좌표에서 방을 돌렸다고 가정을 하면

행 : 1000 => 1

열 : 0100 => 2

가 될것입니다.

 

이 상태에서 현재 방의 타입은 행의 0번째 비트 = 1 , 열의 1번째 비트 = 1이므로 시계방향으로 두번 돌아갔기때문에  방은 돌아가지 않은 원상태입니다.

 

그러면 이상태에서 다음좌표인 (0,2)의 방은 어떤상태가 될까요?

행의 0번째 비트 = 1, 열의 2번째 비트 = 0 이 되기때문에 (0,2)의 방은 시계방향으로 한번 돌아간 상태가 됩니다.

 

그림으로 설명하면 다음과 같습니다.

빨간 선이 돌아간 행과 열을 의미합니다. 따라서 (0,1)의 좌표는 두번 돌아갔고, (0,2)의 좌표는 한번 돌아간것을 알 수 있습니다.

 

이런 원리를 이용해서 O(1)의 시간으로 현재 방의 타입과 다음으로 갈 방의 타입을 알 수 있게됩니다.

 

현재 방의 타입과 다음방의 타입을 알면 갈 수 있는지에 대한 경우를 구할 수 있으므로, BFS를 돌려서 문제를 해결해주면 됩니다.

코드

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 Main {
    static int visited[][][][] = new int[1 << 7][1 << 7][7][7];
    static char maze[][] = new char[7][7];
    static int mv[][] = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    static boolean isIn(int n, int m, int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    static boolean canGo(char from, char to, int direction) {
        if (direction == 0 || direction == 1) {//오른쪽,왼쪽
            if (from == 'A' || from == 'D') {
                return to == 'A' || to == 'D';
            } else return false;
        } else {//위쪽, 아래쪽
            if (from == 'A' || from == 'C') {
                return to == 'A' || to == 'C';
            } else return false;
        }
    }

    static char getRoomType(int row, int col, int x, int y) {
        boolean isTurn = ((row & (1 << x)) == 0 ^ (col & (1 << y)) == 0);
        if (!isTurn) return maze[x][y];
        else {
            switch (maze[x][y]) {
                case 'A':
                case 'B':
                    return maze[x][y];
                case 'C':
                    return 'D';
                case 'D':
                    return 'C';
                default:
                    return ' ';
            }
        }
    }

    static class Node {
        int row, col, x, y;

        public Node(int row, int col, int x, int y) {
            this.row = row;
            this.col = col;
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(st.nextToken());
        int m = Integer.valueOf(st.nextToken());

        for (int i = 0; i < n; i++) {
            maze[i] = br.readLine().toCharArray();
        }

        //초기화
        for (int i = 0; i < 1 << 7; i++) {
            for (int j = 0; j < 1 << 7; j++) {
                for (int x = 0; x < 7; x++) {
                    for (int y = 0; y < 7; y++) {
                        visited[i][j][x][y] = -1;
                    }
                }
            }
        }

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 0, 0, 0));
        visited[0][0][0][0] = 0;

        int answer = Integer.MAX_VALUE;

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

            int row = node.row;
            int col = node.col;
            int x = node.x;
            int y = node.y;
            char nowRoomType = getRoomType(row, col, x, y);

            if (x == n - 1 && y == m - 1) {
                answer = Math.min(answer, visited[row][col][x][y]);
                continue;
            }

            //안돌리고 움직일 수 있는경우
            for (int d = 0; d < 4; d++) {
                int nx = x + mv[d][0];
                int ny = y + mv[d][1];
                if (!isIn(n, m, nx, ny)) continue;//범위 밖이면 건너뛰기

                char nextRoomType = getRoomType(row, col, nx, ny);
                if (canGo(nowRoomType, nextRoomType, d) && visited[row][col][nx][ny] == -1) {
                    visited[row][col][nx][ny] = visited[row][col][x][y] + 1;
                    q.offer(new Node(row, col, nx, ny));
                }
            }

            //해당 자리를 돌리는 경우
            int turnRow = row ^ (1 << x);
            int turnCol = col ^ (1 << y);
            if (visited[turnRow][turnCol][x][y] == -1) {
                visited[turnRow][turnCol][x][y] = visited[row][col][x][y] + 1;
                q.offer(new Node(turnRow, turnCol, x, y));
            }
        }
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
}