[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

1. 문제 접근

문제의 궁극적인 목표는 '0'(출발지)에서 '가장 가까운 1'(도착지)로 갈 때, 이동 횟수의 최솟값을 구하는 것이다.

 

단, 몇가지 제약 사항이 존재한다.

1. 벽으로는 절대 이동할 수 없다.
2. 빈칸은 언제나 이동할 수 있다.
3. 총 6개의 열쇠('a', 'b',  'c',  'd',  'e',  'f')가 존재하고, 각 열쇠는 6개의 문( 'A', 'B',  'C',  'D',  'E',  'F' )를 열 수 있다.

즉, 열쇠를 얻고, 문을 여는 것에 대한 탐색을 어떻게 할 것인지가 관건이다.

 

탐색을 진행하며 만나는 중요한 지점은 2가지다.

1. 4방 탐색을 진행한 결과 문을 만난다.
2. 4방 탐색을 진행한 결과 열쇠를 만난다.

문을 만나게 되면, 확인해야하는 것은 "현재 상태에 해당 문에 대한 열쇠를 가지고 있는가?" 이다.

하지만 현재 열쇠가 없다고 미래에 역시 없다는 것은 보장할 수 없다.

이후 BFS 탐색을 진행하며 해당 문에 맞는 열쇠를 찾을 수도 있기 떄문이다.

 

따라서 열쇠를 만나게 되면 지금까지 탐색을 마친 지점이라도 열 수 있는 문이 있을 수 있기에 다시 탐색을 진행해야한다.

 

맵의 크기는 50 X 50으로 최대 2,500의 크기이며, 6개의 열쇠로 구성할 수 있는 열쇠의 조합은 총 64개가 된다.

 

따라서 높이가 64로 고정인 3차원 방문 배열(`isVisited[64][N][M]`)를 사용하면 된다.

 

해당 배열이 의미하는 것은 "[N, M]위치에 (0 ~ 63)번째 열쇠 조합을 소지하고 방문한 적이 있는가?"이다.

 

열쇠 조합의 경우 비트마스킹을 사용하면 쉽게 접근 할 수 있다.

 

열쇠마다 1bit씩 총 6bit 할당하게 되며, a = 1 / b = 2 / c = 4 / d = 8 / e = 16 / f = 32 와 같은 형태가 된다.

 

예를 들어 비트 상태가 "0 1 1 1 0 0"이라면, 이는 c, d, e 열쇠를 소지한 상태라는 것을 의미한다.

 

따라서 열쇠를 만난다면 만난 열쇠와 비트OR 연산을 통해 합산한 뒤 다시 탐색을 진행하면 된다.

static final char[] keys = {'a', 'b', 'c', 'd', 'e', 'f'};

char nextChar = map[nextRow][nextCol];

// 4. 키
for (int idx = 0; idx < keys.length; ++idx) {
    if(nextChar == keys[idx]) {
        // 키 합치기
        nextKeyStatus = (int) Math.pow(2, (int) doors[idx] - 'A') | nextKeyStatus;
        if(!isVisited[nextKeyStatus][nextRow][nextCol]) {
            isVisited[nextKeyStatus][nextRow][nextCol] = true;
            q.offer(new State(nextRow, nextCol, nextDist, nextKeyStatus));
        }else {
            break;
        }
    }
}

또한, 문을 만난다면 현재 가지고 있는 열쇠 조합과 비트AND 연산을 통해 0보다 크다면 문을 열 수 있다고 판단할 수 있다.

static final char[] doors = {'A', 'B', 'C', 'D', 'E', 'F'};

char nextChar = map[nextRow][nextCol];

// 3. 문
for (int idx = 0; idx < doors.length; ++idx) {
    if (nextChar == doors[idx]) {
        // 현재 그 키를 가지고 있다
        if (((int) Math.pow(2, (int) doors[idx] - 'A') & currKeyStatus) > 0) {
            if (!isVisited[nextKeyStatus][nextRow][nextCol]) {
                isVisited[nextKeyStatus][nextRow][nextCol] = true;
                q.offer(new State(nextRow, nextCol, nextDist, nextKeyStatus));
            }
        }
        // 현재 그 키를 가지고 있지 않다
        else {
            break;
        }
    }
}

 

최종적으로 종료지점을 만나면 이동거리를 출력하고 종료한다.

 

---

2. 코드

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

/**
 * [BOJ] - 달이 차오른다, 가자. / 1194번
 * @author JinHxxxxKim
 * 
 * BFS
 * 
 * 조건1: 열쇠를 얻어야 대응하는 문을 들어갈 수 있다.
 * 조건2: 0->1로 가는 최단 경로를 구해야한다.
 * 
 * a = 1 / b = 2 / c = 4 / d = 8 / e = 16 / f = 32
 * 
 * 1. 맵 정보를 입력받는다. 
 *   1-1. 0을 입력 받으면, State Class에 row, col을 저장한다.
 * 2. visted 배열은 64 x N x N 의 3차원 배열로 설정한다. 
 * 3. 열쇠는 비트마스킹을 통해 저장한다.
 * 4. 시작점에서 BFS를 실행한다.
 *   4-1. 현재 열쇠 조합에서 4방 탐색을 실행한다.
 *     4-1-1. 현재 열쇠 조합으로 방문한 적이 없다면 Queue에 offer
 *     4-1-2. 현재 열쇠 조합으로 방문한 적이 있다면, PASS
 *   4-2. 다음 노드의 경우의 수
 *     - 벽: PASS
 *     - 열쇠: 현재 열쇠 조합 | 만나 열쇠 => 새로운 열쇠 조합을 만든다.
 *     - 문: 현재 열쇠 조합에서 통과할 수 있는 문인지 검증한다.
 *     - 빈칸: 방문한적이 없다면 Queue offer
 *     - 출구: 최단 경로를 출력하고 저장한다.
 * 
 */
public class Solution {
	static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static final int[] dx = {-1, 1, 0, 0};
	static final int[] dy = {0, 0, -1, 1};
	static final char[] keys = {'a', 'b', 'c', 'd', 'e', 'f'};
	static final char[] doors = {'A', 'B', 'C', 'D', 'E', 'F'};
	static final char WALL = '#';
	static final char FLOOR = '.';
	static final char EXIT = '1';
	
	static char[][] map;
	static boolean[][][] isVisited;
	static int N, M;
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		isVisited = new boolean[64][N][M]; // 열쇠를 가지고 있을 수 있는 조합은 총 64가지

		State startState = null;
		// 맵 입력
		for (int row = 0; row < N; ++row) {
			String rowInfo = br.readLine().trim();
			for (int col = 0; col < M; ++col) {
				char currChar = rowInfo.charAt(col);
				if (currChar == '0') {
					// 시작점 저장
					startState = new State(row, col, 0, 0);
					map[row][col] = '.';
				}else {
					map[row][col] = currChar;
				}
			}
		}
        
		// 로직 시작
		Queue<State> q = new ArrayDeque<>();
		q.offer(startState);
		isVisited[0][startState.row][startState.col] = true;
		while(!q.isEmpty()) {
			State currNode = q.poll();
			int currRow = currNode.row;
			int currCol = currNode.col;
			int currDist = currNode.dist;
			int currKeyStatus = currNode.keyStatus;

			// 4방 탐색
			for (int dir = 0; dir < 4; ++dir) {
				int nextRow = currRow + dx[dir];
				int nextCol = currCol + dy[dir];
				int nextDist = currDist + 1;
				int nextKeyStatus = currKeyStatus;

				// 범위 검증
				if (nextCol < 0 || nextRow < 0 || nextCol >= M || nextRow >= N)
					continue;
				// 나올 수 있는 경우의 수 확인
				char nextChar = map[nextRow][nextCol];

				// 1. 벽
				if (nextChar == WALL) {
					continue;
				}
				// 2. 빈칸
				else if (nextChar == FLOOR) {
					if (!isVisited[nextKeyStatus][nextRow][nextCol]) {
						isVisited[nextKeyStatus][nextRow][nextCol] = true;
						q.offer(new State(nextRow, nextCol, nextDist, nextKeyStatus));
					}
					continue;
				}
				// 3. 문
				for (int idx = 0; idx < doors.length; ++idx) {
					if (nextChar == doors[idx]) {
						// 현재 그 키를 가지고 있다
						if (((int) Math.pow(2, (int) doors[idx] - 'A') & currKeyStatus) > 0) {
							if (!isVisited[nextKeyStatus][nextRow][nextCol]) {
								isVisited[nextKeyStatus][nextRow][nextCol] = true;
								q.offer(new State(nextRow, nextCol, nextDist, nextKeyStatus));
							}
						}
						// 현재 그 키를 가지고 있지 않다
						else {
							break;
						}
					}
				}
				// 4. 키
				for (int idx = 0; idx < keys.length; ++idx) {
					if(nextChar == keys[idx]) {
						// 키 합치기
						nextKeyStatus = (int) Math.pow(2, (int) doors[idx] - 'A') | nextKeyStatus;
						if(!isVisited[nextKeyStatus][nextRow][nextCol]) {
							isVisited[nextKeyStatus][nextRow][nextCol] = true;
							q.offer(new State(nextRow, nextCol, nextDist, nextKeyStatus));
						}else {
							break;
						}
					}
				}
				// 5. 출구
				if(nextChar == EXIT) {
					System.out.println(nextDist);
					return;
				}
			}
		}
		System.out.println(-1);
	}

	static class State {
		int row, col;
		int dist;
		int keyStatus;

		public State(int row, int col, int dist, int keyStatus) {
			super();
			this.row = row;
			this.col = col;
			this.dist = dist;
			this.keyStatus = keyStatus;
		}

		@Override
		public String toString() {
			return "State [row=" + row + ", col=" + col + ", dist=" + dist + ", keyStatus=" + keyStatus + "]";
		}
		
	}
}

---

3. 디버깅

3차원 방문 배열을 사용하는 것, 비트 마스킹을 통해 조금 더 쉽게 문제에 접근 할 수 있다.

 

백준 벽 부수고 이동하기 시리즈를 풀어 본 것이 3차원 방문 배열을 사용하는 것에 도움을 많이 준 것 같다.

---

4. 결과