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

• #1194 달이 차오른다, 가자
• 문제 풀이  
  • BFS + 비트마스크
  • Key, Door
  • 구상
• 풀이 코드 

#1194 달이 차오른다, 가자

난이도 : 골드 1

유형 : BFS / 비트마스크

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

▸ 문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

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

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

▸ 출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

 

 

문제 풀이  

BFS + 비트마스크

제목이 이상해서 다른 문제를 풀려고하다가 2021 카카오 인턴 코테 4번 문제와 유형이 비슷하여 풀이를 하였다. 

 

카카오 문제는 우선순위 큐를 활용한 다익스트라 + 비트마스크의 유형이었다면 해당 문제는 그와 비슷한 BFS + 비트마스크 문제이다.

* BFS와 다익스트라의 차이는 그래프에 가중치가 있고 없고의 차이라고 보면 된다.

 

해당 문제는 단순 BFS문제에서 key와 door라는 장치만 추가되었다고 볼 수 있다.

 

Key, Door

총 6가지의 key와 door는 각 쌍을 이룬다. 영식이는 그래프를 움직일 때 마다 키를 지니고있는지 없는지 상태 여부를 체크해줘야 한다. 그래야 문을 만났을 때 해당 문을 통과할 수 있는지 없는지 판단할 수 있기 때문이다.

 

key의 상태 표현은 비트마스킹을 활용해 줄 것이다. 비트마스킹은 메모리 사용도 줄이고 간결하게 코딩을 할 수 있다는 장점을 가지고 있다,

// 배열
boolean[] keyStatus = {1,1,0,0, ...};

// 비트마스킹
int keyStatus = 1100...;

 

구상

영식이가 길을 걷다가 마주할 상황은 총 4가지이다.

1. '#' 벽을 만난다 
2. '.' 그냥 길을 걷는다. 
3. 'a'~'f' key를 줍는다. 
4. 'A'~'F' 문을 마주한다. 

1,2번 케이스

1,2번은 그냥 BFS탐색과 똑같이 '#' 벽을 만나면 경로 탐색은 종료하고, '.' 을 만나면 계속해서 탐색을 진행한다.

 

3번 케이스

'a'~'f'에 맞는 key의 상태를 업데이트해준다. 

int nextStatus = key|status; // key 상태 업데이트

 

4번 케이스

4번 현재 영식이가 지닌 key의 상태를 확인하여 해당 문을 열 수 있는지 확인한다.

if(status & key = key){
	// true이면 문을 열 수 있으므로 탐색진행
	// false이면 해당 문을 열 수 없으므로 탐색 종료
}

 

그리고 '1'을 만나면 탐색을 종료해주면 된다. '1'은 맵에 1개 이상 존재하므로 좌표로 특정지어서는 안된다.

 

풀이 코드 

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n,m;
	static int[][] map;
	static Map<Integer, Integer> key;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int answer = -1;
	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());
		
		map = new int[n][m];
		key = new HashMap<>();
		int start_x=0, start_y=0;
		for(int i=0; i<n; i++) {
			String line = br.readLine();
			// '#': 0, '.': 11, '0':13, '1':14, 
			// 'a' 62 ~ 'f' 67
			// 'A' 30 ~ 'F' 35
			for(int j=0; j<m; j++) {
				int num = line.charAt(j)-35;
				if(num == 13) {
					start_x = j;
					start_y = i;
				}
				else if(num>61 && num <68) { // key 저장 
					if(!key.containsKey(num)) {
						key.put(num, 1<<(num-61));
					}
				}
				map[i][j] = num;
			}
		}
		
		bfs(start_x, start_y);
		System.out.println(answer);
	}
	static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][][] visited = new boolean[n][m][1<<7];
		q.add(new int[] {x,y,0,0});
		visited[y][x][0] = true;
		
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			int px = pos[0];
			int py = pos[1];
			int status = pos[2];
			int move = pos[3];
			
			if(map[py][px] == 14) {
				answer = move;
				return;
			}
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx <0 || ny<0 || nx>m-1 || ny>n-1 ) continue;
				if(map[ny][nx] == 0 || visited[ny][nx][status]) continue; 
				int nStatus = status;
				
				// key 획득 
				if(map[ny][nx]>61 && map[ny][nx] <68) {
					nStatus = status|key.get(map[ny][nx]); // Key 상태 업데이트 
					if(!visited[ny][nx][nStatus]) {
						visited[ny][nx][nStatus] = true;
						q.add(new int[] {nx,ny,nStatus, move+1});
					}
				}
				// door 마주침 
				else if(map[ny][nx]>29 &&map[ny][nx] <36) {
					if(!key.containsKey(map[ny][nx]+32)) continue; // key가 맵에 존재하지 않으면 pass
					// 현재 지닌 key와 문 일치하면 탐색 진행
					if((status & key.get(map[ny][nx]+32)) == key.get(map[ny][nx]+32)) {
						visited[ny][nx][nStatus] = true;
						q.add(new int[] {nx,ny,nStatus, move+1});
					}
				}
				// 그냥 길 
				else {
					visited[ny][nx][nStatus] = true;
					q.add(new int[] {nx,ny,nStatus,move+1});
				}
			}
			
		}
	}
}