[백준] 1194. 달이 차오른다, 가자 - 골드5

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

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

 

문제 요약

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다. 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

문제 해결 아이디어

비트 마스킹

비트 마스킹 기법은 대충 뭔지 이론적으로는 알고 있었지만 어떻게 쓰이는지는 잘 몰랐는데, 이 문제를 풀면서 어떻게 적용하는지 알게 되었다.

처음에 이 문제를 봤을 때 당연히 bfs로 접근해야겠다고 생각했고, 단순히 key를 획득했는지, 획득하지 않았는지를 boolean 1차원 배열로 체크해 주면 되겠다고 생각했다.

하지만 그렇게 풀다 보니 맞닥뜨린 문제는 1. 그동안 풀었던 bfs 문제와는 달리 배열을 여러 번 왔다갔다 할 수 있었고, 2. 그렇다 보니 key를 쥐고 이동하는 것과 아무것도 없는 상태로 이동하는 것에 대한 차이가 있었다는 것이다.

이러한 문제를 해결하기 위해 visited 배열을 3차원으로 이용하는데, 여기서 비트마스킹이 적용된다.

key의 획득 여부를 저장하기 위한 3차원 영역에는 1 << 6, 즉 1000000을 저장하게 되는데, 만약 a키를 획득한다면 1/10000이 key로 저장될 것이고, b키를 획득한다면 1/010000이 저장될 것이다.

키를 획득한다면 비트 OR 연산으로 key를 저장한다. 즉, 내가 a키를 쥐고 있는 상황에서 b키도 획득한다면 1/110000이 key값으로 저장될 것이다. 

문을 만나게 되었을 때 key를 가지고 있는지 확인하려면 비트 AND 연산을 사용하면 된다. A문을 만난다면 key값과 1이 AND 연산을 진행한다. 즉, 문의 위치에 해당되는 부분이 1인 상태다. 비트 AND 연산은 모두 1일 경우에 1이 나오고, 하나라도 0이 있으면 0이 나오는 연산이다. 만약 연산 결과가 0이라면 해당되는 문과 AND 연산을 진행한 것이므로 key가 0이라는 소리이기 때문에 해당 문의 열쇠가 없다는 뜻이다. 

key 비트 값은 획득할 때마다 갱신되고, 그 값을 가지고 visited 배열 또한 갱신하기 때문에 상황에 따른 방문 관리를 해 줄 수 있다.

 

비트 마스킹에 대한 개념이 확실하지 않아서 애를 먹었던 부분은 while문을 돌면서 큐에 저장된 좌표를 하나씩 체크해 주는데, key를 획득했을 경우에 다음 좌표로 넘겼을 때 key값을 갱신해야 된다는 부분이었다.

이게 무슨 말이냐면 열쇠를 주우면 key값을 바로 갱신하게 했는데, 그 때문에 네 방향 탐색을 하면서 다음 좌표에 넣을 때 아직 열쇠가 없는 상황에서 전의 방향에서 열쇠를 주웠다고 다음 방향도 이미 주운 것처럼 queue에 넣게 되는 경우가 있었다. (쓰면서도 설명이 잘 안되네...) 

그러니까 간단히 말하자면 current를 가지고 네방향 탐색을 할 때는 서로의 열쇠 획득 여부가 영향을 주어서는 안 된다. 다음으로 넘겨야 된다! int key = current[2]; 코드를 for 문 안에 넣었을 때와 밖에 넣었을 때의 차이를 깨달았다.

(예시. current가 0,1이고 0,0에 열쇠가 있는 경우 current 네방향 탐색이 끝나지 않은 상태에서 0,0에서 열쇠를 주웠다고 0,2탐색을 할때 0,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_백준_1194_달이차오른다가자 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		char[][] maze = new char[N][M];
//		boolean[][] visited = new boolean[N][M];
//		boolean[] key = new boolean[6]; // a-f
		// 키를 들고있을 때랑 아닐때랑 visited 관리를 따로 해줘야한다
		boolean[][][] visited = new boolean[N][M][1 << 6]; // a키를 갖고 있는 경우 100000 b키를 갖고있는경우 010000 이런식
		Queue<int[]> q = new LinkedList<int[]>();

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			maze[i] = str.toCharArray();
			for (int j = 0; j < M; j++) {
				if (maze[i][j] == '0') {
					q.offer(new int[] { i, j, 0, 0 });
					visited[i][j][0] = true;
				}
			}
		}

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };

		while (q.size() > 0) {
			int[] current = q.poll();
			// int key = current[2]; // 여기 있을때랑
			int cnt = current[3];
			for (int i = 0; i < 4; i++) {
				int nr = current[0] + dr[i];
				int nc = current[1] + dc[i];
				int key = current[2]; /// 여기 있을때의 차이 ㅠㅠ
				// 열쇠를 주웠을 때 key값이 변하기 때문에...!! 
				if (maze[current[0]][current[1]] == '1') {
					System.out.println(cnt);
					return;
				}

				if (nr < 0 || nr >= N || nc < 0 || nc >= M || maze[nr][nc] == '#' || visited[nr][nc][key])
					continue;

				if (maze[nr][nc] >= 'a' && maze[nr][nc] <= 'f') { // 열쇠이면
					key |= 1 << (maze[nr][nc] - 'a'); // 키의 비트값 구하기 (몇번째 키인지)
				} else if (maze[nr][nc] >= 'A' && maze[nr][nc] <= 'F') { // 문이면
					int num = maze[nr][nc] - 'A'; // 몇번째 문인지 번호
					if (((1 << num) & key) == 0) // and연산을 해서 0라는 것은 해당 문의 키가 없다는 것
						continue;
				}
				visited[nr][nc][key] = true;
				q.offer(new int[] { nr, nc, key, cnt + 1 });
			}
		}
		System.out.println(-1);
	}
}