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

문제 링크 : https://www.acmicpc.net/problem/1194

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

 

문제 해결 방법

bfs와 비트마스킹을 사용하여 구현했다.

keys 배열을 생각해내는데 오래 걸렸다.

 

"abcdef" 키 에서

a 키를 갖고 있다면 000001

a, d키를 갖고 있다면 001001로 비트마스킹 처리한 값을 keys 배열의 세 번째 index 값으로 접근한다.

 

package com.BOJ;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class boj1194_달이차오른다가자 {

    static class Node {
        int r;
        int c;
        int key;

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

    static int N;
    static int M;
    static char[][] map;
    static boolean[][][] keys;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    static String lower = "abcdef";
    static String upper = "ABCDEF";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new char[N][M];
        keys = new boolean[N][M][(int)Math.pow(2, 6)];

        int startR = 0;
        int startC = 0;

        sc.nextLine();
        for (int i = 0; i < N; i++) {
            map[i] = sc.nextLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (map[i][j] == '0') {
                    startR = i;
                    startC = j;
                }
            }
        }

        Node start = new Node(startR, startC, 0);
        System.out.println(bfs(start));
    }

    public static int bfs(Node start) {
        Queue<Node> q = new LinkedList<>();
        q.add(start);
        keys[start.r][start.c][0] = true;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                int curR = node.r;
                int curC = node.c;
                int curKey = node.key;

                if (map[curR][curC] == '1') return cnt;

                for (int j = 0; j < 4; j++) {
                    int nextR = curR + dr[j];
                    int nextC = curC + dc[j];
                    int key = curKey;

                    if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M || map[nextR][nextC] == '#') continue;

                    if (lower.indexOf(map[nextR][nextC]) >= 0) {
                        key |= (1 << map[nextR][nextC] - 'a');
                    } else if (upper.indexOf(map[nextR][nextC]) >= 0) {
                        if ((key & (1 << (map[nextR][nextC] - 'A'))) == 0) {
                            continue;
                        }
                    }

                    if (keys[nextR][nextC][key]) continue;

                    keys[nextR][nextC][key] = true;
                    q.add(new Node(nextR, nextC, key));
                }
            }
            cnt++;
        }
        return 0;
    }
}