[BFS/비트마스킹]달이차오른다, 가자(백준 1194번, 자바)

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

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

 

3차원 visit 배열을 사용 visit[x][y][열쇠 보유 상태]

-> 열쇠 보유 상태는 비트 마스킹

 

 

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 N, M;
	static char[][] d;
	static char[][] dp;
	static int[] dx= {0,1,0,-1};
	static int[] dy= {1,0,-1,0};
	static Queue<Point> q;
	static boolean[][][] visit;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in ));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		q=new LinkedList<>();
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		d=new char[N][M];
		dp=new char[N][M];
		
		Point departPos=null;
		visit=new boolean[N][M][1<<6];
		
		for(int i=0;i<N;i++) {
			d[i]=(br.readLine()).toCharArray();
		}
	
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(d[i][j]=='0') 
					departPos=new Point(i,j,0,0);
				
			}
		}
		int answer=bfs(departPos.x, departPos.y);
		System.out.println(answer);
		
	}
	
	static int bfs(int x, int y) {
		
		visit[x][y][0]=true;
		q.add(new Point(x,y,0,0));
		
		while(!q.isEmpty()) {
			
			Point p=q.poll();
			//System.out.println(p.x +" "+p.y+" "+p.key+ " "+p.cnt);
			
			
			
			for(int i=0;i<4;i++) {	
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				int key=p.key;
				int key1=key;
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;//좌표가 범위를 벗어난 경우 
				if(d[nx][ny]=='#' || visit[nx][ny][key]) continue; //벽인 경우 
				
				if(d[nx][ny]=='1')  return p.cnt+1; //도착한 경우
				
				
				if(d[nx][ny]>='a' && d[nx][ny]<='f') { //열쇠를 습득할 수 있는 상태
				 
					key |= (1<<d[nx][ny]-'a'); 
					visit[nx][ny][key]=true;
					q.add(new Point(nx, ny,key, p.cnt+1));
					continue;
				}
		
				
				if(d[nx][ny]>='A' && d[nx][ny]<='F') { 
					if((key & (1 << d[nx][ny]-'A'))!=0) { //열쇠를 소장하고 있다면
						visit[nx][ny][key]=true;
						q.add(new Point(nx, ny,key, p.cnt+1));
					}
					continue;
				}
				visit[nx][ny][key]=true;	
				q.add(new Point(nx,ny,key,p.cnt+1));
				key=key1;
			}
			//key=key1;
		}
		return -1;
	}
	
	
	static class Point {
		
		int x;
		int y;
		int key;
		int cnt;
		
		public Point(int x, int y, int key, int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.key=key;
			this.cnt=cnt;
		}

	
	}

}