본문 바로가기

Dot Algo∙ DS/PS

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

    #1194 달이 차오른다, 가자

    난이도 : 골드 1

    유형 : BFS / 비트마스크

     

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

    첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

    www.acmicpc.net

    ▸ 문제

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

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

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

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

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

    • 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
    • 벽 : 절대 이동할 수 없다. (‘#’)
    • 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (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});
    				}
    			}
    			
    		}
    	}
    }