[백준] 1194. 달이 차오른다, 가자. (그래프 탐색/Java)

[BOJ] 1194. 달이 차오른다, 가자

 

📌 풀이 과정

이 문제도 백준의 1600. 말이 되고픈 원숭이 문제처럼 3차원 방문 배열 아이디어를 떠올려야 한다.

 

각 좌표에서 민식이가 어떤 키를 가지고 있는지 관리해야 하기 때문에

민식이가 열쇠와 문을 사용하는 상태를 관리하려면, 3차원 방문 배열이 필요하다.

즉, (x, y) 위치에서 열쇠를 가지고 있는 상태에 따라
서로 다른 경로로 이동할 수 있으므로 열쇠 상태를 포함한 방문 체크가 필요하다.

 

visited[x][y][key]로, (x, y) 좌표에서 특정한 key 상태로 방문한 적이 있는지를 기록한다.

key 상태는 이진수로 표현하여, 열쇠의 소지 여부를 6비트로 나타낸다.

 

💡 비트로 키 관리하기

문제에서 키는 a, b, c, d, e, f로 총 6개다.

6개의 키를 사용할 때 필요한 비트 수는 6비트이며, 6비트로 표현할 수 있는 값의 범위는

000000부터 111111까지로, 총 64가지(2^6)의 상태를 나타낼 수 있다.

 

예를 들어

• 000000: 키가 하나도 없는 상태
• 000001: a 키만 있는 상태
• 000011: a와 b 키가 있는 상태
• 111111: 모든 키(a, b, c, d, e, f)를 가지고 있는 상태

이렇게 키의 모든 가능한 조합을 표현할 수 있다.

 

✨ 제출 코드

메모리 : 16764 KB

시간 : 116 ms

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[][] map;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	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];
		
		int x = 0, y = 0;
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			for(int j = 0; j < M; j++) {
				if(line.charAt(j) == '0') {
					x = i; y = j;
				}
			}
			map[i] = line.toCharArray();
		}
		
		map[x][y] = '.';
		System.out.println(escapeMaze(x, y));
		
	}
	
	private static int escapeMaze(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {x, y, 0, 0});
		boolean[][][] visited = new boolean[N][M][64];
		visited[x][y][0] = true;
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			x = cur[0];
			y = cur[1];
			int key = cur[2]; // 현재 열쇠 상태
			int depth = cur[3]; // 이동한 거리
			
			if(map[x][y] == '1') return depth;
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				
				char next = map[nx][ny];
				if(next == '#') continue; // 벽인 경우
				
				int newKey = key;
				if(next >= 'a' && next <= 'f') { // 열쇠인 경우 열쇠 얻기
					newKey |= (1 << (next - 'a'));
				}
				
				if(next >= 'A' && next <= 'F') { // 문인 경우 열쇠가 없으면 지나갈 수 없다.
					if((key & (1 << next - 'A')) == 0) continue;
				}
				
				if(!visited[nx][ny][newKey]) {
					visited[nx][ny][newKey] = true;
					q.offer(new int[] {nx, ny, newKey, depth + 1});
				}
			}
		}
		
		return -1;
	}

}