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

달이 차오른다, 가자.

풀이

이동을 하는 것은 bfs로 처리하면 된다.

하지만 이 때 방문체크를 어떤 식으로 처리해야 할지가 큰 고민이었다.

민식이는 열쇠들을 가지고 있을 수 있기 때문에 열쇠의 상태에따라 방문체크를 해주면 되겠다는 생각을 했다.

그런데 열쇠의 소지 여부를 배열로 관리하다보니 방문위치에서의 문의 여부와 그리고 열쇠의 상태에 대해서 연산을 하기 어려웠다.

그래서 다른 방법을 찾아보니 비트마스크를 통해 열쇠의 상태를 관리할 수 있었다.

현재 열쇠 상태에서 습득한 열쇠 - 'a'를 한 값을 or 연산을 해서 열쇠의 상태를 얻을 수 있었다.

열쇠의 종류는 총 6개이고 그렇기 때문에 2^6개의 visit 배열을 만들어 방문체크를 해준다면 문제를 풀 수 있다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    static char[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line;
        line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        map = new char[n][m];
        Queue<Pair> queue = new LinkedList<>();

        char[] temp;
        for (int i = 0; i < n; i++) {
            temp = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                map[i][j] = temp[j];
                if (map[i][j] == '0') {
                    queue.offer(new Pair(i, j, 0, 0));
                }
            }
        }
        bw.write(bfs(queue) + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static int bfs(Queue<Pair> queue) {
        boolean[][][] visit = new boolean[n][m][64];
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            visit[p.x][p.y][p.key] = true;
            if (map[p.x][p.y] == '1') {
                return p.cnt;
            }

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m)) {
                    if (!visit[nx][ny][p.key] && map[nx][ny] != '#') {
                        //'key'
                        if (map[nx][ny] - 'a' >= 0 && map[nx][ny] - 'a' < 6) {
                            int key = (1 << (map[nx][ny] - 'a')) | p.key;
                            if (!visit[nx][ny][key]) {
                                visit[nx][ny][key] = true;
                                visit[nx][ny][p.key] = true;
                                queue.offer(new Pair(nx, ny, p.cnt + 1, key));
                            }
                        }
                        //'door'
                        else if (map[nx][ny] - 'A' >= 0 && map[nx][ny] - 'A' < 6) {
                            int door = (1 << (map[nx][ny] - 'A')) & p.key;
                            if (door > 0) {
                                visit[nx][ny][p.key] = true;
                                queue.offer(new Pair(nx, ny, p.cnt + 1, p.key));
                            }
                        }
                        else {
                            visit[nx][ny][p.key] = true;
                            queue.offer(new Pair(nx, ny, p.cnt + 1, p.key));
                        }
                    }
                }
            }
        }
        return -1;
    }
}

class Pair {
    int x;
    int y;
    int cnt;
    int key;

    public Pair(int x, int y, int cnt, int key) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.key = key;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "x=" + x +
                ", y=" + y +
                ", cnt=" + cnt +
                ", key=" + key +
                '}';
    }
}