[BOJ] 백준 [1194] 달이 차오른다, 가자. JAVA

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

1194번: 달이 차오른다, 가자.

문제

풀이

아 .. 비트마스킹이란걸 몰라서 한참을 헤매었다.. 

결론적으로는 열쇠의 유무를 2^6 = 64 , 즉 visit배열을 3차원으로 열쇠유무까지 추가하면 => visit[높이][너비][열쇠]

visit[h][w][64] 이렇게 두고 풀어야 한다는 것이다.

열쇠면 | 연산으로 추가 , 문 이면 & 연산으로 확인하는 식으로해서 탐색을 하면 된다.

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static int w,h;
    static char[][] map;
    static boolean[][][] visit;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        h = Integer.parseInt(input[0]);
        w = Integer.parseInt(input[1]);
        map = new char[h][w];
        visit = new boolean[h][w][64];
        Point start;
        LinkedList<Point> queue = new LinkedList<>();
 
        for (int i = 0; i < h; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j=0;j<w;j++) {
                if (map[i][j] == '0') {
                    queue.add(new Point(j, i, 0, 0));
                    visit[i][j][0]=true;
                }
            }
        }
 
        while (!queue.isEmpty()){
            Point poll = queue.poll();
            if(map[poll.y][poll.x] == '1'){
                System.out.println(poll.cnt);
                return;
            }
            for(int i=0;i<dx.length;i++){
                int nextX = poll.x+dx[i];
                int nextY = poll.y+dy[i];
                if(!isRange(nextX,nextY) || isWall(nextX,nextY) || visit[nextY][nextX][poll.keyCnt])
                    continue;
                if(isKey(nextX,nextY)){
                    int tempKey = (1<<(map[nextY][nextX] - 'a')) | poll.keyCnt;
 
                    if(!visit[nextY][nextX][tempKey]){
                        visit[nextY][nextX][tempKey] = true;
                        visit[nextY][nextX][poll.keyCnt] = true;
                        queue.add(new Point(nextX,nextY,poll.cnt+1,tempKey));
                    }
                }else if(isDoor(nextX,nextY)){
                    int tempDoor = (1 << (map[nextY][nextX] - 'A')) & poll.keyCnt;
 
                    if (tempDoor > 0) {
                        visit[nextY][nextX][poll.keyCnt] = true;
                        queue.add(new Point(nextX,nextY, poll.cnt+1, poll.keyCnt));
                    }
                }else{
                    visit[nextY][nextX][poll.keyCnt] = true;
                    queue.add(new Point(nextX,nextY, poll.cnt+1, poll.keyCnt));
                }
            }
 
        }
        System.out.println(-1);
    }
    static boolean isDoor(int x,int y){
        return map[y][x]>='A'&&map[y][x]<='F';
    }
    static boolean isKey(int x,int y){
        return map[y][x]>='a'&&map[y][x]<='f';
    }
    static boolean isWall(int x,int y){
        return map[y][x]=='#';
    }
    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<w&&y<h;
    }
    static class Point {
        int x,y;
        int cnt;
        int keyCnt;
        public Point(int x, int y, int cnt, int keyCnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.keyCnt = keyCnt;
        }
    }
}