[백준] 1194번 : 달이 차오른다, 가자. - 자바(Java)

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

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

 

문제 해석

직사각형의 미로는 다음과 같이 구성되어 있다.

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

한 번 움직일때 상하좌우로 움직일 수 있으며 탈출하는데 걸리는 이동 횟수의 최솟값을 구하라.

미로를 탈출할 수 없다면 -1을 출력한다.

문제 풀이 전 설계

미로를 탈출하기 위한 이동횟수의 최솟값을 구하는 문제이므로 BFS가 떠오릅니다.

열쇠/문이라는 개념이 존재하며 출구도 여러 개 있습니다.

또한 열쇠는 획득하게 되면 여러번 사용할 수 있습니다.

 

한번 지나갔던 길이라도 열쇠를 획득하고 다시 돌아가게 된다면 문을 열어 지나갈 수 있을 수도 있습니다.

visited 배열을 visited[y좌표][x좌표][열쇠획득] 으로 두고 완전 탐색 느낌을 구현해야 할 것 같습니다.

초기에는 방향도 설정하려고 했지만 방향은 딱히 설정할 이유는 없을것 같습니다.

여기서 열쇠획득을 설정한 이유는 한번 지나갔던 길이라도 열쇠를 획득하고 다시 가면 다시 탐색할 수 있기 때문입니다.

초기값을 0으로 두고 열쇠 하나를 획득하면 1 두 개를 획득하면 2 이렇게 증가하도록 합니다. ( 초기에는 7개에 대한 순열도 구성하려고 했으나 필요 없을 것 같습니다.)

 

문제 풀이 하면서

결론부터 말하면 비트 마스크 + BFS문제입니다.

 

핵심은 내가 키를 획득했는데 다른 키를 획득하지 못 한 사람이 내 키를 가져가서 들어가 버리는 경우가 존재하면 안 됩니다.

 

예를 들자면 bfsQ가 사방으로 퍼져나가고 있다고 가정해보겠습니다.

왼쪽으로 5칸 가게 되면 문이 있습니다.

오른쪽으로 4칸 가게 되면 열쇠가 있습니다.

그러면 왼쪽으로 4칸, 오른쪽으로 4칸 동시에 퍼져나가면서 열쇠를 획득했는데 이 열쇠를 왼쪽에서 사용해버리면 안 된다는 의미입니다.

 

그렇다고 열쇠를 획득하고 Queue를 초기화한다면 원래 열쇠가 없어도 잘 갈 수 있는 빠른 길이 존재하는 경우를 없애기 때문에 이렇게도 하면 안 됩니다.

 

또한 열쇠를 획득하는 경우에도 keyCount를 증가시키면서 했는데 이 또한 a, f 열쇠를 획득해도 2개 , e, f  열쇠를 획득해도 2개의 visited로 체크되기 때문에 따라서 000000~111111을 활용하여 열쇠의 획득 여부를 나타내야 합니다.

 

100000은 a 열쇠를 획득한 경우를 의미합니다.

111111은 a, b, c, d, e, f 열쇠를 획득한 경우를 의미합니다.

 

따라서 visited [y좌표][x좌표][1<<6]

1<<6은 64를 의미합니다. 2^6

 

핵심 로직은 다음과 같습니다

if (isDoor(tempY, tempX)) {
	// 키가 없다면 지나가지 못함
	// 원리 비트 And 연산 (기존비트 & 문)
	// 즉 비트의 자리수가 아무것도 같지 않으면 열쇠는 없다는 뜻이고 continue
	if ((keyBitMask & (1 << (board[tempY][tempX] - 'A'))) == 0) {
		continue;
	}

}

if (isKey(tempY, tempX)) {
	// 원리 비트 or연산 ( 기존비트 | 새로운 키 획득)
	// 만약 기존비트 000000
	// a키 획득 100000
	// 기존비트 | 새로운 키 획득 = 100000
	keyBitMask = keyBitMask | (1 << (board[tempY][tempX] - 'a'));
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_1194_달이차오른다가자 {

	static char[][] board;
	static boolean[][][] visited;
	static final int DIRECTION = 4;
	static int N, M;
	static int result = -1;
	static Player startPlayer;
	static int dy[] = { -1, 1, 0, 0 };
	static int dx[] = { 0, 0, -1, 1 };

	static class Player {
		int y;
		int x;
		int depth;
		int keyBitMask;

		public Player(int y, int x, int depth, int keyBitMask) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
			this.keyBitMask = keyBitMask;
		}

		@Override
		public String toString() {
			return "Player [y=" + y + ", x=" + x + ", depth=" + depth + ", keyBitMask=" + keyBitMask + "]";
		}

	}

	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());

		board = new char[N][M];
		visited = new boolean[N][M][1 << 6];

		// String은 불변객체여서 메모리를 많이 먹기 때문에 StringBuilder 활용
		StringBuilder sb = new StringBuilder();
		char tempChar;
		for (int y = 0; y < N; y++) {
			sb.append(br.readLine());
			for (int x = 0; x < M; x++) {
				tempChar = sb.charAt(x);
				board[y][x] = tempChar;

				// 출발지
				if (tempChar == '0') {
					startPlayer = new Player(y, x, 0, 0);
					continue;
				}
			}
			sb.setLength(0);
		}

		bfs();
		System.out.println(result);

	}

	private static void bfs() {
		Queue<Player> bfsQ = new LinkedList<Player>();
		bfsQ.offer(startPlayer);
		visited[startPlayer.y][startPlayer.x][startPlayer.keyBitMask] = true;
		Player tempPlayer;
		int tempY, tempX, depth, keyBitMask;

		while (!bfsQ.isEmpty()) {
			tempPlayer = bfsQ.poll();

			for (int k = 0; k < DIRECTION; k++) {
				tempY = tempPlayer.y + dy[k];
				tempX = tempPlayer.x + dx[k];
				keyBitMask = tempPlayer.keyBitMask;
				depth = tempPlayer.depth;

				if (!isValid(tempY, tempX, keyBitMask)) {
					continue;
				}

				if (isDestination(tempY, tempX)) {
					result = depth + 1;
					return;
				}

				// 만약 문이라면
				if (isDoor(tempY, tempX)) {
					// 키가 없다면 지나가지 못함
					// 원리 비트 And 연산 (기존비트 & 문)
					// 즉 비트의 자리수가 아무것도 같지 않으면 열쇠는 없다는 뜻이고 continue
					if ((keyBitMask & (1 << (board[tempY][tempX] - 'A'))) == 0) {
						continue;
					}

				}

				if (isKey(tempY, tempX)) {
					// 원리 비트 or연산 ( 기존비트 | 새로운 키 획득)
					// 만약 기존비트 000000
					// a키 획득 100000
					// 기존비트 | 새로운 키 획득 = 100000
					keyBitMask = keyBitMask | (1 << (board[tempY][tempX] - 'a'));
				}

				visited[tempY][tempX][keyBitMask] = true;
				bfsQ.add(new Player(tempY, tempX, depth + 1, keyBitMask));
			}
		}

	}

	private static boolean isValid(int tempY, int tempX, int keyBitMask) {
		// 좌표가 유효해야 함 && 지나갈 위치가 #이 아니여야 함 && 방문되지 않았어야 함 && 문으로 막혀있다면 키가 존재해야함
		return tempY >= 0 && tempY < N && tempX >= 0 && tempX < M && board[tempY][tempX] != '#'
				&& !visited[tempY][tempX][keyBitMask];
	}

	private static boolean isDestination(int tempY, int tempX) {
		return board[tempY][tempX] == '1';
	}

	private static boolean isDoor(int tempY, int tempX) {
		return board[tempY][tempX] >= 'A' && board[tempY][tempX] <= 'F';
	}

	private static boolean isKey(int tempY, int tempX) {
		return board[tempY][tempX] >= 'a' && board[tempY][tempX] <= 'f';
	}
}