[백준] 1194 달이 차오른다, 가자. - BFS + 비트마스크 JAVA

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

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

코드설명

BFS와 비트마스크 문제입니다.

 

처음에 문제를 봤을때는, 다음의 코드와 같이 visited를 8차원 배열로 선언하여 진행하려고했습니다. 이떄 Node에는 현재 가지고 있는 열쇠를 계속 가지고 다니기 위해 Node 객체에 해당 boolean 형으로 추가가 필요합니다. 혹은 HashSet이나 HashMap으로도 진행할 수 있습니다. ( 열쇠를 한번 가지면 계속가지고 있습니다. ) 

public static boolean[][][][][][] visited = new boolean[N][M][2][2][2][2][2][2];

class Node{
	int r;
    int c;
    boolean a;
    boolean b;
    boolean c;
    boolean d;
    boolean f;
    boolean g; 
    //혹은 HashSet을 사용
    public Node(){
    
    }
}

위와 같이 진행하는것도 충분히 가능하지만, 만약 열쇠가 알파벳 숫자만큼 26개가 있을경우는 위의 경우로 해결하는것이 매우 비효율적일 것 입니다.

 

비트마스크를 활용하여 현재 가지고 있는 열쇠들을 체크하는 방안이 훨씬 코드로 짜기 쉽고, 적은 메모리를 사용하는 방식일 것 입니다.

 

열쇠를 만났을떄의 비트마스킹 시프팅 방식은 다음과 같습니다.

int nkeyBitMask = 1 << (map[nr][nc] - 'a');  // 1에서 비트시프팅을 진행합니다. 'a'라면 0만큼 bit shift, 'b'라면 1만큼 bit shift. 이렇게 처리함으로써 새로 만난 key의 종류를 파악할 수 있습니다.
nkeyBitMask = nkeyBitMask | keyBitMask; // OR 연산으로 이전열쇠와 현재 받은 열쇠를 합칩니다.

문을 만났을때의 비트마스크 시프팅 방식은 다음과 같습니다.

int doorBitMask = 1 << (map[nr][nc] - 'A');
int isAccesable = doorBitMask & keyBitMask; //만약 doorBitMask & keyBitMask 에서 0보다 크다면, 해당 문에 해당하는 키가 존재한다는 뜻.

 

전체적인 로직은 주석에 담아보았습니다.

 

코드

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 {
	public static int N, M;
	public static char[][] map; 
	public static boolean[][][] visited;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static Node start;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer 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][64];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '0') {
    				start = new Node(i, j, 0, 0);
    			}
    		}
    	}
    	
    	simulate();
    	if(answer == 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);
    	}
    }
	
	public static void simulate() {
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		visited[start.r][start.c][start.keyBitMask]= true;
		while(!q.isEmpty()) {
			Node temp = q.poll();
			int r = temp.r;
			int c = temp.c;
			int keyBitMask = temp.keyBitMask;
			int cnt = temp.cnt;
			
			if(map[r][c] == '1') { //만약 '1'이라면 종료조건 처리합니다. 
				answer = cnt;
				return ;
			}
			for(int dir=0;dir<4;dir++) {
				int nr = r + dx[dir];
				int nc = c + dy[dir];
				
				if( nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(visited[nr][nc][keyBitMask] == true) continue;
				if(map[nr][nc] == '.' || map[nr][nc] == '0' || map[nr][nc] == '1') {
					
					visited[nr][nc][keyBitMask] = true;
					q.offer(new Node(nr, nc, keyBitMask, cnt + 1));
				}else if(map[nr][nc] >= 'a' && map[nr][nc] <= 'z') { //만약 열쇠를 만날경우 비트마스킹으로 처리
					int nkeyBitMask = 1 << (map[nr][nc] - 'a');  // 1에서 비트시프팅을 진행합니다. 'a'라면 0만큼 bit shift, 'b'라면 1만큼 bit shift. 이렇게 처리함으로써 새로 만난 key의 종류를 파악할 수 있습니다.
					nkeyBitMask = nkeyBitMask | keyBitMask; // OR 연산으로 이전열쇠와 현재 받은 열쇠를 합칩니다.
					if(visited[nr][nc][nkeyBitMask] == false ) {
						visited[nr][nc][nkeyBitMask] = true; 
						visited[nr][nc][keyBitMask] = true;
						q.offer(new Node(nr, nc, nkeyBitMask, cnt + 1));
					}
				}else if(map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') {
					int doorBitMask = 1 << (map[nr][nc] - 'A');
					int isAccesable = doorBitMask & keyBitMask; //만약 doorBitMask & keyBitMask 에서 0보다 크다면, 해당 문에 해당하는 키가 존재한다는 뜻.
					if(isAccesable > 0) {
						visited[nr][nc][keyBitMask] = true;
						q.offer(new Node(nr, nc, keyBitMask, cnt + 1));
					}
				}
			}
		}
	}

}

class Node{
	int r;
	int c;
	int keyBitMask; //비트마스킹
	int cnt; //이동횟수
	public Node(int r, int c, int keyBitMask, int cnt) {
		this.r=r;
		this.c=c;
		this.keyBitMask=keyBitMask;
		this.cnt=cnt;
	}
}