백준 1194 - Java (BFS,비트마스킹)

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

 

풀이

 

이 문제를 보면 기본적으로 bfs를 사용해서 풀 수 있겠다는 생각이 든다.

하지만 어려운 부분은 바로

a, b, c, d ,e ,f 라는 열쇠와 그에 대응하는

A, B, C, D, E, F 라는 문에 대해서이다. 

이에 이진법으로 각 열쇠마다 아래와 같이 대입한다

a= 1(2), b = 10(2), c = 100(2) 

...

그럼 a와 c열쇠를 가지고 있다면 101(2)이 되는것이다.!

그렇다면 a,c열쇠를 가진 상태를 정수로 하면 5가 될것이다.

int now = 5 // 현재 가진 열쇠정보

A라는 문을 만난다면 아래 조건식처럼 계산하면 된다

// 예제코드 문에 해당하는 열쇠검사1
if ((now & (1 << ('A' - 'A'))) == 0){ // A문에 해당하는 열쇠있나 검사
	// 문에 해당하는 열쇠없음
    continue;
}
// 예제코드 문에 해당하는 열쇠검사2
if ((now & (1 << ('B' - 'A'))) == 0){ // B문에 해당하는 열쇠있나 검사
	// 문에 해당하는 열쇠없음
    continue;
}

 

그리고 a~f 까지면 111111(2) 이기 때문에 접근을 제어하는 3차원 배열을 아래와 같이 선언한다.

문을 열었다면 true가 될 것.

boolean[][][] visited = new boolean[n][m][64]

 

주의점으로 나는 처음에 해당 배열을 사용하지 않고 큐에 [ 좌표정보와 키값, 이동거리] 가 들어있는데

큐에 poll()한 요소의 키값으로만 제어하려고하니 문제가 생겼다. 이것 때문에 아주 긴 시간 헤맸다..

 

전체코드

import java.util.*;
class Main {
    static Queue<int[]> q;
    static char[][] board;
    static int n, m, sy, sx;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int bfs() {
        boolean[][][] visited = new boolean[n][m][64]; // 열쇠 상태를 포함한 방문 배열
        visited[sy][sx][0] = true; // 시작점 방문 처리
        q.offer(new int[]{sy, sx, 0, 0}); // 좌표(y, x), 이동거리, 열쇠 상태

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int y = cur[0];
            int x = cur[1];
            int dist = cur[2];
            int keys = cur[3];
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if (board[ny][nx] == '#') continue; // 벽이면 스킵
                if (board[ny][nx] == '1') {
                    return dist + 1; // 출구를 찾으면 거리 반환
                }
                int newKeys = keys;
                // 소문자이면 열쇠를 얻음
                if (board[ny][nx] >= 'a' && board[ny][nx] <= 'f') {
                    newKeys = (newKeys | (1 << (board[ny][nx] - 'a')));
                }
                // 대문자이면 열쇠가 있는지 확인
                if (board[ny][nx] >= 'A' && board[ny][nx] <= 'F') {
                    if ((newKeys & (1 << (board[ny][nx] - 'A'))) == 0) {
                        continue; // 열쇠가 없으면 스킵
                    }
                }
                // 새로운 위치이거나 열쇠 상태에서 처음 방문하는 경우
                if (!visited[ny][nx][newKeys]) {
                    visited[ny][nx][newKeys] = true; // 방문 처리
                    q.offer(new int[]{ny, nx, dist + 1, newKeys});
                }
            }
        }

        return -1; // 출구를 찾을 수 없으면 -1 반환
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        q = new LinkedList<>();
        board = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j);
                if (board[i][j] == '0') {
                    sy = i;
                    sx = j;
                }
            }
        }

        System.out.println(bfs());
    }
}