[JAVA] BOJ 백준 1194 달이 차오른다, 가자

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

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

비트마스킹과 BFS를 활용해야 하는 문제이다.
1. visited를 3차원 배열로 선언하여 현재 x, y와 key의 상태를 가지고 방문했는지를 판단해준다.
2. 다음 위치가 key인 경우 가지고 있는 key정보를 갱신한다.
3. 다음 위치가 문인 경우 현재 key 중 문을 열 수 있는 경우 열어준다.
4. 빈 공간인 경우 원래처럼 visited만 갱신한다.
5. 전부 queue에 넣는다.

전체 코드

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

public class BOJ_1194{
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		char[][] maze = new char[N][M];
		int sx = 0, sy = 0;
		for(int i=0; i<N; i++) {
			String s = bf.readLine();
			for(int j=0; j<M; j++) {
				maze[i][j] = s.charAt(j);
				if(maze[i][j] == '0') { sx = i; sy = j;}
			}
		}
		ArrayDeque<int[]> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[N][M][64];
		q.offer(new int[] {sx, sy, 0, 0}); //현재 위치, 이동 횟수, 열쇠 가짐 여부
		v[sx][sy][0] = true;
		while(!q.isEmpty()) {
			int[] now = q.poll();
			if(maze[now[0]][now[1]] == '1') {
				System.out.println(now[2]);
				return;
			}
			f: for(int d=0; d<4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if(nx < 0 || ny < 0 || nx >=N || ny >= M || maze[nx][ny] == '#' || v[nx][ny][now[3]]) continue;
				int key = now[3];
				if(maze[nx][ny] <= 'F' && maze[nx][ny] >= 'A') {
					if((key & 1<<(maze[nx][ny] - 'A')) > 0) {
						v[nx][ny][now[3]] = true;
					}
					else continue f;
				}
				else if(maze[nx][ny] <= 'f' && maze[nx][ny] >= 'a') {
					key |= 1<<(maze[nx][ny]-'a');
					v[nx][ny][key] = true;
				}
				else
					v[nx][ny][now[3]] = true;
				q.offer(new int[] {nx, ny, now[2]+1, key});
			}
		}
		System.out.println(-1);
		
	}
}

더 자세한 코드 설명

boolean[][][] v = new boolean[N][M][64];
q.offer(new int[] {sx, sy, 0, 0}); //현재 위치, 이동 횟수, 열쇠 가짐 여부
v[sx][sy][0] = true;
while(!q.isEmpty()) {
	int[] now = q.poll();
	if(maze[now[0]][now[1]] == '1') {
		System.out.println(now[2]);
		return;
	}
	f: for(int d=0; d<4; d++) {
		int nx = now[0] + dx[d];
		int ny = now[1] + dy[d];
		if(nx < 0 || ny < 0 || nx >=N || ny >= M || maze[nx][ny] == '#' || v[nx][ny][now[3]]) continue;
		int key = now[3];
		if(maze[nx][ny] <= 'F' && maze[nx][ny] >= 'A') {
			if((key & 1<<(maze[nx][ny] - 'A')) > 0) {
				v[nx][ny][now[3]] = true;
			}
			else continue f;
		}
		else if(maze[nx][ny] <= 'f' && maze[nx][ny] >= 'a') {
			key |= 1<<(maze[nx][ny]-'a');
			v[nx][ny][key] = true;
		}
		else
			v[nx][ny][now[3]] = true;
		q.offer(new int[] {nx, ny, now[2]+1, key});
	}
}
System.out.println(-1);

먼저 키는 6개이므로 총 2^6 = 64개의 상태가 존재할 수 있다. 그러므로 visited를 N, M, 64에 대해 정의한다.

입력 시 저장해둔 현재 위치 정보를 q에 넣고 지금은 가진 키가 없기 때문에 0일때를 visited true로 만든다.

while문 실행 시 1(출구)에 도달한 경우 시간 정보를 출력하고 return 한다.

4방을 탐색한다. → 격자를 벗어나는지 확인한다. → maze의 벽인지 확인한다. → 현재 키를 가지고 자리를 방문하였는지 확인한다.

다음과 같은 확인이 끝났으면 이동이 가능한 곳의 후보가 된다!(다 되는 것은 아님!!! → 문인데 열쇠가 없는 경우)

1. 문인 경우
   1. 해당하는 키가 있는 지 비트마스킹으로 확인한다. 우리는 A-F로 저장되어있기 때문에 A로 빼주어야 0-5라는 원하는 값이 나온다.
   2. &로 해당하는 자리가 1인지 확인해준다.
   3. 있으면 visited 갱신 없으면 다음 방향을 조사하러 continue 해준다.
2. 열쇠인 경우
   1. key 정보를 갱신한다.
   2. visited도 갱신한다.
3. 빈 공간인 경우 visited만 갱신한다.
4. 다음 3가지 경우 모두 q에 넣어준다. 이때 key를 먼저 변수에 따로 저장한 뒤 갱신이 필요한 곳에서만 값을 바꿔주었다.