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

이 문제는 BFS를 응용하는 문제이다.

문제에서 a~f까지 키가 주어지는데 이것을 가지고 있는 상태에서 움직여야한다. 그래서 비트연산을 통하여 각 Pos클래스에 가지도록 변수 alp를 선언해주었고, 열쇠를 가진상태에서 방문또한 변화가있으므로 visit배열도 3차원으로 visit[R][C][1<<6]으로 잡고 문제를 구하였다. BFS를 돌면서 열쇠 a~f를 만나면 현재 alp에 비트연산을 통하여 값을 주었고, 문인 A~F를 만난다면 비트연산을 통해 변수를 가지고 있다면 방문할수 있도록 코드를 작성하였다.

BFS의 심화형태이기 때문에 다시한번 풀어볼 필요가 있는 문제이다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_1194_달이차오른다가자 {
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static char[][] map;
    static boolean[][][] visit;
    static int R,C;
    static int answer;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j,alp,distance;
        Pos(int i,int j,int a,int d){
            this.i=i;this.j=j;alp=a;distance=d;
        }
    }
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        map=new char[R][C];
        queue=new LinkedList<>();
        visit=new boolean[R][C][1<<6];
        
        for(int i=0;i<R;i++) {
            String str=br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j]=str.charAt(j);
                if(map[i][j]=='0') {
                    queue.offer(new Pos(i, j, 0, 0));
                    visit[i][j][0]=true;
                    map[i][j]='.';
                }
            }
        }
        
        answer=Integer.MAX_VALUE;
        bfs();
        if(answer==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(answer);
        
    }
    
    static void bfs() {
        while(!queue.isEmpty()) {
            Pos cur=queue.poll();
//            System.out.println(cur.i+","+cur.j+","+cur.alp+","+cur.distance+", >> "+map[cur.i][cur.j]);
            
            if(map[cur.i][cur.j]=='1') {
                answer=Math.min(cur.distance, answer);
                continue;
            }
            
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                
                if(nextI<0 || nextI>=R || nextJ<0 ||nextJ>=C)
                    continue;
                
                //일반땅.
                if(map[nextI][nextJ]=='.' && visit[nextI][nextJ][cur.alp]==false) {
                    queue.offer(new Pos(nextI, nextJ, cur.alp, cur.distance+1));
                    visit[nextI][nextJ][cur.alp]=true;
                }
                
                //열쇠
                if('a'<=map[nextI][nextJ] && map[nextI][nextJ]<='f' && visit[nextI][nextJ][cur.alp]==false) {
                    queue.offer(new Pos(nextI, nextJ, cur.alp|(1<<map[nextI][nextJ]-'a'), cur.distance+1));
                    visit[nextI][nextJ][cur.alp]=true;
                }
                
                //문
                if('A'<=map[nextI][nextJ]&&map[nextI][nextJ]<='F' && (cur.alp & (1<<map[nextI][nextJ]-'A'))!=0 && visit[nextI][nextJ][cur.alp]==false) {
                    queue.offer(new Pos(nextI, nextJ, cur.alp, cur.distance+1));
                    visit[nextI][nextJ][cur.alp]=true;
                }
                
                //탈출구
                if(map[nextI][nextJ]=='1' && visit[nextI][nextJ][cur.alp]==false) {
                    queue.offer(new Pos(nextI, nextJ, cur.alp, cur.distance+1));
                    visit[nextI][nextJ][cur.alp]=true;
                }
            }
        }
    }
}