[1194] 달이 차오른다, 가자. - Java[자바]

 

 

 

| 문제 링크

 

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

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

 

 

 

 

---

 

 

 

 

| 문제

 

 

 

1. 미로를 탐색해 탈출할 수 있는 최소 이동 횟수를 출력하는 문제로 문(대문자 알파벳)과 열쇠(소문자 알파벳)가 등장하며, 열쇠를 습득한 상태에서만 해당하는 문을 열고 지나갈 수 있습니다. 입력값은 아래와 같습니다.
   
   • 빈 칸: 언제나 이동할 수 있다. ('.')
   • 벽: 절대 이동할 수 없다. ('#')
   • 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
   • 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
   • 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
   • 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
2. 동일한 열쇠와 문이 여러번 나올 수 있으며, 열쇠는 여러 번 사용할 수 있습니다.

 

 

 

 

---

 

 

 

 

 

| 풀이

 

 

1. 최단 이동 횟수를 찾는 문제로 bfs 방식으로 풀었으며, bfs 문제는 방문처리가 가장 중요합니다. 해당 문제에서는 3차원 배열 방문처리를 통해 좌표와 열쇠를 가지고있는 상태마다 방문처리를 진행했습니다.
2. 열쇠는 총 6개(a,b,c,d,e,f)로 열쇠를 가지고 있을 수 있는 경우의 수는 총 64가지로 방문 배열을 boolean[n][m][64]으로 생성해줍니다.
3. 매번 if를 통해 64가지의 경우를 나누어 주는 것은 비효율적으로, 각 비트마스킹을 이용해 아래와 같이 경우의 수를 관리해줍니다.
   
   000000: 아무 열쇠도 가지고 있지 않은 경우
   000001(=2^0): a열쇠만 가지고 있는 경우
   000010(=2^1): b열쇠만 가지고 있는 경우
   ...
   100000(=32): f열쇠만 가지고 있는 경우
   111111(=64): a,b,c,d,e,f 열쇠를 모두 가지고 있는 경우
   
   
4. 문을 만났을 때, 해당 열쇠를 가지고 있는지 확인하며 열쇠가 있는 경우 해당 열쇠 상태에 맞는 boolean 배열에 방문처리를 해줍니다.
5. 열쇠를 만났을 때, 비트연산자 or 기능을 통해 현재 열쇠 상태와 병합해 줍니다.
6. 출구(=1)을 만난 경우에는 누적된 cnt를 return하고, bfs가 끝났으나 출구를 만나지 못한 경우 -1을 return해줍니다.

 

 

 

 

---

 

 

 

 

 

| 코드

 

 

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

class Minsick{
    int r;
    int c;
    int cnt;
    int key;
    
    public Minsick() {
    }

    public Minsick(int r, int c, int cnt, int key) {
        this.r = r;
        this.c = c;
        this.cnt = cnt;
        this.key = key;
    }
    
}

public class Main {
    
    public static int n;
    public static int m;
    public static char[][] maze;
    public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}};
    
    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());
        maze = new char[n][m];
        
        int[] start = new int[2];
        char point = '.';
        for(int r = 0; r<n; r++) {
            String str = br.readLine();
            for(int c = 0; c<m; c++) {
                point=str.charAt(c);
                maze[r][c] = point;
                if(point=='0') {
                    start[0]=r;
                    start[1]=c;
                }
            }
        }
        
        bw.write(String.valueOf(bfs(start[0],start[1])));
        br.close();
        bw.close();
        
    }
    
    public static int bfs(int row, int col) {
        Queue<Minsick> que = new LinkedList<>();
        //a,b,c,d,e,f 6가지 열쇠를 가지고 있는 경우의 수는 64가지
        boolean[][][] flag = new boolean[n][m][64];
        que.add(new Minsick(row,col,0,0));
        
        int answer = -1;
        while(!que.isEmpty()) {
            Minsick temp = que.poll();
            int r = temp.r;
            int c = temp.c;
            
            for(int i = 0; i<4; i++) {
                int dr = r + delta[i][0];
                int dc = c + delta[i][1];
                int cnt = temp.cnt;
                int key = temp.key;
                
                if(dr<0 || dr>=n || dc<0 || dc>=m || flag[dr][dc][key] || maze[dr][dc]=='#')
                    continue;
                if(maze[dr][dc]=='1') {
                	return cnt+1;
                }
                //열쇠를 만났을 때
                if('a' <= maze[dr][dc] && maze[dr][dc] <= 'f') {
                	//만난 열쇠의 비트 추출
                	int tempKey = 1 << (maze[dr][dc] - 'a');
                	//현재 열쇠와 만난 열쇠 or 조건으로 병합
                	key = key | tempKey;
                }
                //문을 만났을 때
                else if('A' <= maze[dr][dc] && maze[dr][dc] <= 'F' && ((key & 1 << (maze[dr][dc]-'A'))==0)) {
                	//key: 열쇠를 보유한 상황 000000(열쇠 없음) 부터 111111(모든 열쇠 있음)까지 
                	//&: 비트의 각 자리별로 비교하였을 때 둘 다 1인 경우 1을 출력
                	//1 << maze[dr][dc] - 'A': 1에 maze[dr][dc]-'A'를 곱한 숫자의 비트마스킹(1,2,3,4,5,6 는 각각 열쇠 a,b,c,d,e,f를 뜻함)
                	continue;
                }
                flag[dr][dc][key] = true;
                que.add(new Minsick(dr,dc,cnt+1,key));
            }
        }
        return answer;
    }

}