[백준/boj] 1194: 달이 차오른다, 가자. (JAVA) / 비트마스킹 / BFS

문제

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

풀이

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M;
	static char[][] map;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static boolean[][][] visited;
	
	private static class Pos {
		int x;
		int y;
		int keyStatus;
		int move;
		
		public Pos(int x, int y, int keyStatus, int move) {
			this.x = x;
			this.y =y;
			this.keyStatus = keyStatus;
			this.move = move;
		}
	}
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M][1<<6];
		
		Pos start = null;
		for(int i=0; i<N; i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0; j<M; j++) {
				if(map[i][j] == '0') {
					start = new Pos(i, j, 0, 0);
				}
			}
		}
		
		System.out.println(bfs(start.x, start.y));
	}

	private static int bfs(int x, int y) {
		Deque<Pos> deque = new ArrayDeque<>();
		deque.add(new Pos(x, y, 0, 0));
		
		while(!deque.isEmpty()) {
			Pos pos = deque.poll();
			
			for(int i=0;i<4; i++) {
				int nx = pos.x + dx[i];
				int ny = pos.y + dy[i];
				int keyStatus = pos.keyStatus;
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		
				if(map[nx][ny] == '1' ) {
					return pos.move + 1;
				}
				
				if(map[nx][ny] == '#') continue;
				
				if(visited[nx][ny][pos.keyStatus]) continue;
				
				if(map[nx][ny] >= 'a' && map[nx][ny] <= 'f') { // key 
					keyStatus |= (1 << (map[nx][ny] - 'a'));
				}
				
				if(map[nx][ny] >= 'A' && map[nx][ny] <= 'F' ) { // door
					if((pos.keyStatus & (1 << map[nx][ny]- 'A')) == 0) {
						continue;
					}
				}
				
				deque.add(new Pos(nx, ny, keyStatus, pos.move+1));
				visited[nx][ny][keyStatus] = true;
			}
		}

		return -1;
	}
}

keyStatus 초기값은 000000이고, 가지고 있는 키의 상태를 나타낸다. 

앞에서부터 FEDCBA문에 해당하는 키(fedcba) 존재 여부를 나타내며, 1이면 키를 가지고 있다는 뜻이다. 아래는 몇몇 예시이다.

000001

a 키를 가지고 있는 상태

000010

b 키를 가지고 있는 상태

000111

a,b,c 키를 가지고 있는 상태

100011

a,b,f 키를 가지고 있는 상태

110000

e,f 키를 가지고 있는 상태

keyStatus |= (1 << (map[nx][ny] - 'a'));

keyStatus가 000000이고 map[nx][ny] 가 'b'면 keyStatus는 OR 비트 연산을 통해 000010 이 된다.

if((pos.keyStatus & (1 << map[nx][ny]- 'A')) == 0) 

map[nx][ny]가 문일 때, pos.keyStatus가 해당 문의 키인지 확인한다 0이라는 것은 해당 문의 키가 아닌 것을 의미한다. 

문이 0010 이고, 키가 0001이면 0 이 나오기 때문이다.