백준 9328번: 열쇠 (JAVA)

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

9328번: 열쇠

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

---

 

풀이

'달이 차오른다, 가자'랑 유사한 문제이다. 다만 차이점으로는, 여기는 문이 26개이기 때문에 현재 열쇠의 상태를 비트마스킹으로 저장해도 2^26= 3200만이 나오기에, bfs에서 가능한 모든 상태(행, 열, 열쇠 상태)를 배열에 저장했다가는 메모리 초과가 발생할 것이다. 

따라서, 외곽에서 들어온 후 새로운 열쇠를 먹으면 새로 bfs를 돌리면 된다: 열쇠는 26개이기에, 한 테스트케이스 당 최대 26번의 bfs를 돌면 된다. 빌딩 배열의 크기가 최대 10000이기에, 여유있을 것이다.

 

틀린 이유

아이디어 생각해놓고, '건물 외부에서 침입하는 건 빈 칸으로만 가능하다'라는 고정관념이 머리속에 자리잡아 틀렸다. 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            // 외부에서 들어오는 처리를 위해
            char[][] map = new char[M+2][N+2];
            for (int i = 1; i <= M; i++) {
                String str = br.readLine();
                for (int j = 1; j <= N; j++) {
                    map[i][j] = str.charAt(j-1);
                }
            }

            int key = 0;
            String str = br.readLine();
            if (str.charAt(0) != '0') {
                for (int i = 0; i < str.length(); i++) {
                    key |= (1<<(str.charAt(i)-'a'));
                }
            }

            Queue<int[]> queue = new ArrayDeque<>();
            int ans = 0;
            int curKey = key;
            while (true) {
                boolean[][] visited = new boolean[M+2][N+2];
                // 건물 외부를 다 넣어준다: bfs를 통해, 건물 내부로 들어갈 수 있으면 들어갈 것이다.
                for (int i = 1; i <= M; i++) {
                    queue.offer(new int[] {i, 0});
                    queue.offer(new int[] {i, N+1});
                }
                for (int j = 1; j <= N; j++) {
                    queue.offer(new int[] {0, j});
                    queue.offer(new int[] {M+1, j});
                }

                while (!queue.isEmpty()) {
                    int[] cur = queue.poll();
                    int r = cur[0], c = cur[1];
                    for (int i = 0; i < 4; i++) {
                        int nr = r + dr[i], nc = c + dc[i];
                        if (nr < 1 || nr > M || nc < 1 || nc > N) continue;
                        if (visited[nr][nc]) continue;
                        // 1. 열쇠 먹기
                        if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
                            curKey |= (1<<(map[nr][nc]-'a'));
                            map[nr][nc] = '.';
                            visited[nr][nc] = true;
                            queue.offer(new int[] {nr, nc});
                        }
                        // 2. 빈 칸이거나 열 수 있는 문
                        else if (map[nr][nc] == '.' || (map[nr][nc] >= 'A' && map[nr][nc] <= 'Z'
                                && (((curKey & (1<<(map[nr][nc]-'A'))) != 0)))) {
                            map[nr][nc] = '.';
                            visited[nr][nc] = true;
                            queue.offer(new int[] {nr, nc});
                        }
                        // 3. 문서 획득하기
                        else if (map[nr][nc] == '$') {
                            ans++;
                            map[nr][nc] = '.';
                            visited[nr][nc] = true;
                            queue.offer(new int[] {nr, nc});
                        }
                    }
                }
                // 이번 bfs를 돌면서 새로 얻은 열쇠가 없는 경우
                if (key == curKey) break;
                key = curKey;	
            }
            System.out.println(ans);	
        }
    }
}