[BOJ] 1194.달이 차오른다, 가자(BFS, BitMask).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

기본적으로는,

탐색 과정에서 주어진 조건에 맞는 동작을 수행하면 된다.

빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)

벽 : 절대 이동할 수 없다. (‘#’)

열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)

문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)

민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)

출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

단, 추가로 처리해주어야 하는 부분은

가지고 있는 열쇠의 상태를 알기 위해서 비트마스크를 사용해야하는데,

열쇠는 a ~ f, 6 가지의 열쇠가 있고, 현재 어떤 열쇠를 가지고 있는지 체크해주어야 한다.

각 열쇠의 체크는 아래와 같다.

a: 000001

b: 000010

c: 000100

d: 001000

e: 010000

f: 100000

만일 a,c,e,f 열쇠를 가지고 있다면

열쇠의 상태는

110101 가 될 것이다.

6 가지의 열쇠 중 어떤 열쇠는 현재 가지고 있는지 표현하기위해

1 << 6 만큼의 공간(100000)이 필요하고

각 열쇠의 상태마다 visited 처리가 필요하다.

visited = new boolean[N][M][1<<6];

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ1194 {
 
    static int N, M;
    static char map[][];
    static boolean visited[][][];
    static State minsik;
    static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };
 
    static class State {
        // x좌표, y좌표, 현재까지 이동거리, 보유하고 있는 키 정보
        int x, y, dist, key;
        public State(int x, int y, int dist, int key) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.key = key;
        }
    }
    
    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 char[N][M];
        // a~f(6가지)까지 들고있는 열쇠의 종류에 따른 visited 처리
        visited = new boolean[N][M][1<<6];
 
        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') {
                    minsik = new State(i,j,0,0);
                }
            }
        }
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<State> q = new LinkedList<>();
        // 초기 민식이 위치
        q.add(minsik);
        visited[minsik.x][minsik.y][0] = true;
        
        while(!q.isEmpty()) {
            State now = q.poll();
            
            // 탈출구에 도착했을 경우
            if(map[now.x][now.y] == '1') 
                return now.dist;
            
            // 사방으로 이동
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                int curKey = now.key;
                
                // 범위를 넘어갈 경우 pass
                if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;
                // 이미 방문한 곳이라면 pass
                if(visited[xx][yy][now.key]) continue;
                // 이동할 수 없을 경우(벽) pass
                if(map[xx][yy] == '#') continue;    
                // 이미 왔던 곳이라면
                if(visited[xx][yy][curKey]) continue;
                
                // 열쇠가 있을 경우
                if(map[xx][yy] >= 'a' && map[xx][yy] <= 'f') {
                    // 키를 집고 상태를 변경
                    curKey |= (1<<map[xx][yy]-'a');
                }
                // 문이 있을 경우
                if(map[xx][yy] >= 'A' && map[xx][yy] <= 'F') {
                    // 나에게 해당 키가 없다면 pass
                    if((curKey & (1 << (map[xx][yy] - 'A'))) == 0) continue;
                }
                // 그냥 빈 곳일 경우, 그냥 아래 처리 수행
                // 현재 정보를 queue에 add
                q.add(new State(xx, yy, now.dist + 1, curKey));
                // 방문처리
                visited[xx][yy][curKey] = true;
            }
        }
        // 미로를 탈출할 수 없다면
        return -1;
    }
}

* 비트연산 추가 설명

line 83) 현재 보유중인 키를 추가해주는 코드이다.

  curKey |= (1<<map[xx][yy]-'a');

  만일 현재(curKey) c 키만 가지고 있다면 상태는 000100 일 것이다.

  여기서 f 키(100000)를 집는다면 f - 'a' 는 5 이므로 

  1 << 5 연산을 수행하면 100000 가 될 것이다.

  그렇다면 다음으로 아래 연산을 수행하게 될 것이고,

      000100

    | 100000

  --------------

      100100 

  이 될 것이다.

  그렇다면 현재 상태는 c, f 키를 보유중인 상태가 된다.

line 88) 현재 해당 키가 있는지 확인하는 코드이다.

  if((curKey & (1 << (map[xx][yy] - 'A'))) == 0)

  현재 F 문에 도달했다면 F - 'A' 는 5이므로

  1 << 5 연산을 수행하면 100000 가 될 것이다.

  그렇다면 다음으로 아래 연산을 수행하게 될 것이고,

       100100

    &  100000

  --------------

       100000 

  이 될 것이다.

  연산 결과인 100000는 0이 아니므로, 해당 f 키를 가지고 있다는 의미이다.

  만일, f 키가 없다면

       000100

    &  100000

  --------------

       000000 

  결과는 0이 될 것이다.