문제

미로 속에 있는 열쇠를 주워서 문을 열어서 출구를 찾으면 되는 문제이다.
열쇠와 문은 a~f이고 열쇠를 가지지 않은 상태에서는 문을 열 수 없다. 이때 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다.

풀이

원래는 boolean 배열로 key를 관리하려고 했는데 열쇠를 얻고 다시 돌아가거나 열쇠를 얻지 못한 경우를 따로 체크해야해서 비트마스크로 체크했다.

열쇠 a~f를 0000001 ~ 1000000의 경우의 수로 놓고 visited 배열을 3차원으로 선언했다.

• Node 객체는 좌표와 count를 저장한다.
• bfs로 길을 탐색한다.
  다음 좌표가 열쇠일 때
  현재 Key와 or 연산으로 새로운 열쇠를 저장한다.
  해당 좌표에 현재 키를 가지고 방문하지 않은 경우에만 queue에 넣어준다.
  문일 때
  현재 key와 가지고 있는 key를 and 연산해서 일치하는 열쇠가 있는지 검사한다.
  

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1194 {
    static char[][] map;
    static boolean[][][] visited;
    static Node start;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        map = new char[n][m];
        visited = new boolean[n][m][64];

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < m; j++) {
                if (map[i][j] == '0') {
                    start = new Node(i, j, 0, 0);
                }
            }
        }

        bfs(start.x, start.y);
    }

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();

        q.add(new Node(x, y, 0, 0));
        visited[x][y][0] = true;

        while (!q.isEmpty()) {
            Node temp = q.poll();
            int count = temp.count;
            int key = temp.key;

            if (map[temp.x][temp.y] == '1') {
                System.out.println(temp.count);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];

                if (nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length) {
                    continue;
                }

                if (map[nx][ny] == '#' || visited[nx][ny][key]) {
                    continue;
                }

                if (map[nx][ny] - 'a' >= 0 && map[nx][ny] - 'a' < 6) {
                    // 열쇠일 때
                    int tempKey = (1 << (map[nx][ny] - 'a')) | key;

                    if (!visited[nx][ny][tempKey]) {
                        visited[nx][ny][tempKey] = true;
                        visited[nx][ny][key] = true;
                        q.add(new Node(nx, ny, count + 1, tempKey));
                    }
                } else if (map[nx][ny] - 'A' >= 0 && map[nx][ny] - 'A' < 6) {
                    // 문일 떄
                    int tempDoor = (1 << (map[nx][ny] - 'A')) & key;

                    // 일치하는 열쇠가 있으면
                    if (tempDoor > 0) {
                        visited[nx][ny][key] = true;
                        q.add(new Node(nx, ny, count + 1, key));
                    }
                } else {
                    visited[nx][ny][key] = true;
                    q.add(new Node(nx, ny, count + 1, key));
                }
            }
        }

        System.out.println(-1);
    }

    static class Node {
        int x;
        int y;
        int count;
        int key;

        public Node(int x, int y, int count, int key) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.key = key;
        }
    }
}