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

1. 문제

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

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

2. 풀이

• BFS + 비트마스킹으로 해결하는 문제.
• 좌표 평면에서 BFS 혹은 DFS의 이동을 생각할 때, 흔히 방문한 곳을 다시 방문하지 않기 위해 boolean OR Int형으로 2차원 방문 처리 배열을 만들어 처리한다.
• 그러나 이 경우는 조건을 가지지 않고 이동하는 경우에는 편리하나, 조건을 가지고 이동하는 경우에는 따로 조건 처리를 해주거나 그리디한 방식으로 방문 처리 배열을 만들어 해결한다. 
• 이 문제와 비슷한 방식이 "벽 부수고 이동하기"(https://sorryday.tistory.com/89) 문제가 있다. 열쇠를 가지고 이동하는 조건이 있기 때문에 어떤 열쇠를 가지고 이 지점을 방문했는지, 혹은 열쇠를 안 가지고 방문했는지 파악해야한다.
  
  
• 이 포스팅에서는 방문 처리 배열을 3차원 배열로 해결하고자 하며, BFS를 보기 전에 방문 처리를 먼저 살펴보자.
• 문과 열쇠를 비트로 표현하면 다음과 같이 표현할 수 있다.

• 열쇠는 먹을 수도 있고, 안 먹을 수도 있기 때문에 $2^6$개의 방문 처리 요소가 필요하고, 먹었다 혹은 안 먹었다 이기 때문에 boolean형으로 방문 처리 배열을 선언할 수 있다.

boolean[][][] visited = new boolean[열쇠의 여부][미로의 row][미로의 column]

• 그리고 열쇠를 먹었다면 이를 합으로 더하여 이동 객체에 가지고 다닌다면, 내가 열쇠를 어떻게 먹었는지 확인할 수 있다.( 이는 문 혹은 열쇠를 만났을 때 자세히 보자)
  
  
• 이제 BFS를 보면 미로에서 나올 수 있는 경우의 수 크게 다음과 같다.
  
  1. 빈칸을 만나거나 출구를 만나는 것
  2. 벽을 만나는 것
  3. 문 혹은 열쇠를 만나는 것
     
     
• 빈칸을 만나거나 출구를 만나는 것
  • 이때는 그냥 이동할 수 있으므로 해당 좌표를 방문 처리하고 Queue에 넣는다.
  • 출구의 경우 Queue에서 Poll 했을 때 최소 이동 경로를 갱신해주면 된다.
• 벽을 만나는 것
  • 벽을 만났다면 이는 이 좌표로 갈 수 없으므로 4방 좌표 반복문에서 다음 인덱스로 넘어간다.
• 문 혹은 열쇠를 만나는 것
  • 이 경우가 문제의 핵심이라 볼 수 있다.
  • 우리는 열쇠 혹은 문을 비트로 처리하고 열쇠를 먹었다면, 설정해놓은 비트를 이동 객체의 keyHap에 더하여 어떤 열쇠를 먹었는지 확인하도록 했다.
  • 이 합을 이용하여 비트의 & 연산을 하면 문을 지나갈 수 있는 열쇠를 먹었는지 확인할 수 있다.
  • 예제 입력 1번을 보면 (0,0) 위치에 'f' 열쇠가 있고 이를 먹고 (0, 3)의 'F'문에 도달했다고 해보자.
  • 비트 연산의 & 연산은 두 비트의 값이 모두 1일 때 1을 반환한다.
  • 이 때, 문에 해당하는 문자의 비트 값과, 먹은 열쇠의 합을 & 연산했을 때, 이 연산 결과 값이 문에 해당하는 문자의 비트값이 같다면 이는 열쇠를 먹었고, 문을 지나갈 수 있다는 것이다.

 

• 또 열쇠는 한 번만 먹어야 하기 때문에 문을 지날 때와 똑같이 열쇠에 해당하는 문자의 비트 값과, 먹은 열쇠의 합을 & 연산했을 때, 이 연산 결과 값이 열쇠에 해당하는 문자의 비트값이 같다면 이는 이미 이 열쇠를 먹었다는 것이기 때문에 열쇠의 합에 더하지 않는다.
• 다만! 이때는 문의 경우와 달리 지나갈 수는 있기 때문에 Queue에 넣어 처리를 해줘야 한다.
• 이를 코드로 본다면 다음과 같다.
  
  
  
  

3. 소스 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int N, M; // N : 세로, M : 가로
	static char[][] map;
	static boolean[][][] visited; // BFS 방문 배열
	
	static class Point {
		int x;
		int y;
		int move;
		int keyHap;
		
		public Point(int x, int y, int move, int keyHap) {
			this.x = x;
			this.y = y;
			this.move = move;
			this.keyHap = keyHap;
		}
	}
	
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	static int result = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		
		int myX = 0;
		int myY = 0;
		
		// map 구성
		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = input.charAt(j);
				
				// 내 위치 갱신
				if (map[i][j] == '0') {
					myX = i;
					myY = j;
					map[i][j] = '.';
				}
			}
		}
		
		// 내위치에서 BFS 시작
		visited = new boolean[65][N][M];
		moonBFS(myX, myY);
		
		// 출력
		if (result == Integer.MAX_VALUE) {
			bw.write("-1");
		} else {
			bw.write(Integer.toString(result));
		}
		
		bw.flush();
		bw.close();
		br.close();
	}

	// BFS 시작
	private static void moonBFS(int myX, int myY) {
		Queue<Point> q = new ArrayDeque<>();
		q.add(new Point(myX, myY, 0, 0));
		visited[0][myX][myY] = true;
		
		while (!q.isEmpty()) {
			Point poll = q.poll();
			
			if (map[poll.x][poll.y] == '1') {
				result = Math.min(poll.move, result);
			}
			
			for (int i = 0; i < 4; i++) {
				int xf = poll.x + dx[i];
				int yf = poll.y + dy[i];
				
				// 범위 안에 있고, 방문하지 않았음
				if (isAvailable(xf, yf) && !visited[poll.keyHap][xf][yf]) {
					char c = map[xf][yf];
					
					// 빈칸을 만나거나 출구를 만나면
					if (c == '.' || c == '1') {
						visited[poll.keyHap][xf][yf] = true;
						q.add(new Point(xf, yf, poll.move + 1, poll.keyHap));
					} 
					
					// 벽이면 continue;
					else if (c == '#') {
						continue;
					}
					
					// 문 혹은 열쇠 -> a : 97 , z : 122 , A : 65 , Z: 90
					else {
						// 문의 범위
						if (c >= 65 && c <= 90) {
							
							int val = (int)Math.pow(2, c - 65);
							
							// 문을 지나갈 수 있다면
							if ((poll.keyHap & val) == val) {
								visited[poll.keyHap][xf][yf] = true;
								q.add(new Point(xf, yf, poll.move + 1, poll.keyHap));
							}
								
						} else if (c >= 97 && c <= 122) { // 열쇠의 범위
							visited[poll.keyHap][xf][yf] = true;
							
							int keysVal = (int)Math.pow(2, c - 97);
							
							// 열쇠를 이미 먹었다는 것
							if ((poll.keyHap & keysVal) == keysVal) {
								q.add(new Point(xf, yf, poll.move + 1, poll.keyHap));
							} else {
								q.add(new Point(xf, yf, poll.move + 1, poll.keyHap + keysVal));
							}
						}
					}
				}
			}
		}
	}
	
	// 범위에 있는지 판단하는 함수
	private static boolean isAvailable(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}
}

4. 배운점

• 2차원 좌표에서 BFS 혹은 DFS로 탐색한다고 해서 방문 배열은 무조건 2차원 배열이 아니다.
• 조건을 따져서 이동할 경우 3차원 방문 배열을 떠올리자!!
  
  
  

5. 점수

70 / 100