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

 

문제

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

 

알고리즘

그래프, 너비우선탐색(BFS), 비트마스킹

 

풀이

비트마스킹과 BFS를 이용하여 해결하였다.

 

다른 BFS 문제와 유사하지만 알파벳 대문자에 해당하는 문은 알파벳 소문자에 해당하는 키가 있어야 통과할 수 있다는 조건이 있다.

따라서 가지고 있는 키의 종류를 유지하고 있어야하는데 이를 표현할 때 비트마스킹을 사용하였다.

예를 들어 ABE 키를 가지고 있다면 0번째, 1번째, 4번째 키를 가지고 있는 셈이므로 key = 010011 가 된다.

 

이제 다음 문장을 통해 i번째 키를 가지고 있는지 확인할 수 있다.

(1 << i & key) == 0

 

만약 i가 4라면  1 << 4 =  1 0 0 0 0 이고,

abe 키를 가지고 있다면  key =  0 1 0 0 1 1 이므로 and 연산(&) 결과는 다음과 같다.

    1 0 0 0 0
& 0 1 0 0 1 1
--------------
= 0 1 0 0 0 0
= 16

즉 1 << i 와 and 연산했을 때 0이 나온다면 해당 키를 가지고 있지 않은 것이고, 0보다 큰 값이 나온다면 키를 가지고 있는 것이다.

 

 

 

다음은 키를 줍는 코드이다.

key = (key | 1 << i)

 

만약 abe 키가 있는 상태에서 d 키를 줍는다면

key = 0 1 0 0 1 1 이고, i << i 는 1 0 0 0 이므로 or 연산(|) 결과는 다음과 같다.

 

  0 1 0 0 1 1
|     1 0 0 0 
--------------
= 0 1 1 0 1 1

 

따라서 다음 칸이 문일 때와 열쇠일 때 위 과정을 거쳐 진행하면 된다.

 

어떤 열쇠를 가지고있냐에 따라 이미 방문했던 곳도 이동 횟수의 최솟값이 갱신될 수 있다.

따라서 visited 배열로 [y][x][key] 의 3차원 배열 관리한다.

이는 (y, x) 칸에 key 를 가지고 방문한 적이 있는지를 저장하는 것이다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class BOJ_1194 {
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 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(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

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

		int y = -1;
		int x = -1;
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				board[i][j] = str.charAt(j);

				if (board[i][j] == '0') {
					y = i;
					x = j;
					board[i][j] = '.';
				}
			}
		}

		int min = 87_654_321;

		ArrayDeque<Player> deque = new ArrayDeque<>();
		deque.add(new Player(y, x, 0, 0));

		while (!deque.isEmpty()) {

			Player cur = deque.poll();

			for (int i = 0; i < dy.length; i++) {
				int ny = cur.y + dy[i];
				int nx = cur.x + dx[i];

				if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx][cur.key])
					continue;

				visited[ny][nx][cur.key] = true;
				
				if (board[ny][nx] == '1') {
					min = Math.min(min, cur.t + 1);
					continue;
				}
				
				if (board[ny][nx] == '#')
					continue;

				// 문 - 해당 키를 가지고 있지 않다면 continue
				if (board[ny][nx] >= 'A' && board[ny][nx] <= 'F') {
					if ((1 << board[ny][nx] - 'A' & cur.key) == 0)
						continue;
				}

				// 열쇠 줍기
				if (board[ny][nx] >= 'a' && board[ny][nx] <= 'f') {
					deque.add(new Player(ny, nx, cur.t+1, (cur.key | 1 << board[ny][nx] - 'a')));
					continue;
				}

				deque.add(new Player(ny, nx, cur.t+1, cur.key));

			}
		}
		
		if(min == 87_654_321)
			System.out.println(-1);
		else System.out.println(min);
	}

	static class Player {
		int y, x, t, key;

		public Player(int y, int x, int t, int key) {
			this.y = y;
			this.x = x;
			this.t = t;
			this.key = key;
		}
	}
}