[백준] 1194번 : 달이 차오른다, 가자.

문제

www.acmicpc.net/problem/1194

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

문제해결방법

이런 BFS 문제는 보통 방문했는지 체크를 해주기 위해 맵과 동일한 사이즈의 배열을 사용하곤 하는데

이 문제는 동일한 위치를 다시 방문하더라도 다른 종류의 열쇠를 가지고 있을 수 있기 때문에

방문 체크를 위한 배열을 열쇠의 조합만큼 가지고 있어야 한다는게 특징이었다.

열쇠의 조합을 쉽게 체크해주기 위해 a ~ f 까지의 조합을 이진수로 표현해주었다. ( 000000 ~ 111111 )

열쇠를 주웠을 때 체크해줄 열쇠 조합, 또 문에 방문했을 때 문에 대응하는 열쇠를 가지고 있는지 확인해주기 위해 Bit mask 기법을 사용했다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main1194_달이차오른다가자 {
 
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
    public static void main(String[] args) throws Exception {
        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());
        char[][] map = new char[N][M];
        boolean[][][] visited = new boolean[64][N][M];
        int si = 0, sj = 0;
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = s.charAt(j);
                if(map[i][j]=='0') {
                    si = i;
                    sj = j;
                }
            }
        }
        int answer = -1;
        int second = 0;
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.add(new int[] {si, sj, 0});
        visited[0][si][sj] = true;
        loop:while(!q.isEmpty()) {
            int size = q.size();
            for(int s=0; s<size; s++) {
                int[] cur = q.poll();
                int key = cur[2];
                for(int d=0; d<dir.length; d++) {
                    int xx = cur[0]+dir[d][0];
                    int yy = cur[1]+dir[d][1];
                    if(xx>=0 && xx<N && yy>=0 && yy<M && map[xx][yy]!='#' && !visited[key][xx][yy]) {
                        if(map[xx][yy]=='0' || map[xx][yy]=='.') {
                            visited[key][xx][yy] = true;
                            q.add(new int[] {xx, yy, key});
                        } else if(map[xx][yy]>='a' && map[xx][yy]<='f') {
                            int nextKeyValue = key|(1<<(map[xx][yy]-'a'));
                            visited[nextKeyValue][xx][yy] = true;
                            q.add(new int[] {xx, yy, nextKeyValue});
                        } else if(map[xx][yy]>='A' && map[xx][yy]<='F' && (key&(1<<(map[xx][yy]-'A')))>0) {
                            visited[key][xx][yy] = true;
                            q.add(new int[] {xx, yy, key});
                        } else if(map[xx][yy]=='1') {
                            answer = second+1;
                            break loop;
                        }
                    }
                }
            }
            second++;
        }
        System.out.println(answer);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.