BOJ. 1194번. 달이 차오른다 가자

 

    BFS + 비트마스킹 문제다. BFS탐색을 체크할 boolean 배열을 3차원으로 만드는 것에 주의하면 그렇게 어렵지 않다. 왜냐면 각 상황에서 들고있는 키의 상황(몇개를 가지고 있는지, key-state) 가 다를 수 있기 때문이다. 따라서 3차원 체크배열을 선언하고, 각 키를 가지고 있을 때 문 여는 상황을 비트마스크로 비교한다면 꽤 빠른 수행시간으로 문제를 풀 수 있다.

www.acmicpc.net/problem/1194

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

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 BOJ1194달이차오른다가자 {

	static int n,m,ans;
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static char[][] map;
	static boolean[][][] check;
	static Queue<Pos> move = new LinkedList<Pos>();
	static class Pos{
		int y,x,t,key;
		public Pos(int y, int x, int t, int key) {
			super();
			this.y = y;
			this.x = x;
			this.t = t;
			this.key = key;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		check = new boolean[n][m][64];
		for(int i=0; i<n; i++) {
			String in = br.readLine();
			for(int j=0; j<m; j++) {
				map[i][j] = in.charAt(j);
				if(map[i][j]=='0') {
					move.add(new Pos(i,j,0,0));
					check[i][j][0] = true;
				}
			}
		}
		solution();
		System.out.println((ans==0)?-1:ans);
	}
	
	private static void solution() {
		while(!move.isEmpty()) {
			Pos cur = move.poll();
			if(map[cur.y][cur.x]=='1') {
				ans = cur.t;
				break;
			}
			for(int d=0; d<4; d++) {
				int ny = cur.y+dy[d];
				int nx = cur.x+dx[d];
				if(checkBound(ny,nx) && map[ny][nx]!='#' && !check[ny][nx][cur.key]) {
					// 다음위치가 key인 경우( a b c d e f )
					if(  'a' <= map[ny][nx] && map[ny][nx] <= 'f') {
						move.add(new Pos(ny,nx,cur.t+1, (cur.key|(1<<(map[ny][nx]-'a'))) ));
						check[ny][nx][(cur.key|(1<<(map[ny][nx]-'a')))] = true; 
					}
					// 다음 위치가 문인경우( A B C D E F )
					else if( 'A' <= map[ny][nx] && map[ny][nx] <= 'F') {
						if( (cur.key & (1<<(map[ny][nx]-'A'))) > 0 ) { // 키가 있으면
							move.add(new Pos(ny,nx,cur.t+1,cur.key));
							check[ny][nx][cur.key] = true;
						}
					}
					// 아무것도 아닌경우
					else {
						move.add(new Pos(ny,nx,cur.t+1,cur.key));
						check[ny][nx][cur.key] = true;
					}
				}
			}

		}		
		
	}
	
	private static boolean checkBound(int y, int x) {
		return (y>=0&&y<n&&x>=0&&x<m) ? true : false;
	}
	
}