(9328) 열쇠 (Java)

문제

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

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

입력

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

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

'.'는 빈 공간을 나타낸다.
'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
'$'는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

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

출력

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

예제 입력 1

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony
예제 출력 1
3
1
0

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries K번

문제를 번역한 사람: baekjoon
데이터를 추가한 사람: bamgoesn
문제의 오타를 찾은 사람: goooora, na982, vanila_banana

알고리즘 분류

구현
그래프 이론
그래프 탐색
너비 우선 탐색

Solution

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

public class Main {
    public static int tc, h, w, doc;
    public static char[][] bd;
    public static List<Character> keys;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> q;
    public static boolean[][] visited;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static List<Node>[] doors;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        tc = Integer.parseInt(br.readLine());

        for(int t = 0; t < tc; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            // 빌딩 세팅 => bd
            bd = new char[h][w];
            for(int i = 0; i < h; i++) {
                String[] strArr = br.readLine().split("");
                for(int j = 0; j < w; j++) {
                    char ch = strArr[j].charAt(0);
                    bd[i][j] = ch;
                }
            }

            // 최초에 소지한 키 => keys
            String[] keysArr = br.readLine().split("");
            keys = new ArrayList<Character>();
            for(int i = 0; i < keysArr.length; i++) {
                char ch = keysArr[i].charAt(0);
                if(ch != '0') keys.add(ch);
            }

            q = new LinkedList<Node>();
            visited = new boolean[h][w];

            // 키가 없는 문을 담아둘 리스트형 배열 초기화
            doors = new ArrayList[26];
            for(int k = 0; k < doors.length; k++) {
                doors[k] = new ArrayList<Node>();
            }

            // 출발지점 세팅
            doc = 0;
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    // 출발지점 세팅 (가장자리인 경우에만)
                    if(i == 0 || j == 0 || i == h-1 || j == w-1) {
                        // 이미 방문한 적이 있거나, 벽이면 skip
                        if(visited[i][j] || bd[i][j] == '*') continue;

                        // 탐색 진행
                        setNode(i, j);
                    }
                }
            }

            bw.write(String.valueOf(findDoc()) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int findDoc() {
        while(!q.isEmpty()) {
            Node cur = q.poll();

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

                // 빌딩 범위를 벗어나거나, 이미 방문하였거나, 벽이면 skip
                if(isNotRange(nx, ny) || visited[nx][ny] || bd[nx][ny] == '*') continue;

                // 탐색 진행
                setNode(nx, ny);
            }

            // 열쇠가 없어서 못열었던 문 중에 열쇠를 획득하여 이제는 열 수 있는 문이 있는지 확인하고,
            // 열 수 있으면 큐에 담아서 탐색
            for(int i = 0; i < doors.length; i++) {
                char chUpper = (char) ('A' + i);
                char chLower = String.valueOf(chUpper).toLowerCase().charAt(0);
                if(keys.contains(chLower)) {
                    for(int j = 0; j < doors[i].size(); j++) {
                        Node tmp = doors[i].get(j);
                        q.offer(new Node(tmp.x, tmp.y));
                        visited[tmp.x][tmp.y] = true;
                    }
                    doors[i].clear();
                }
            }
        }

        return doc;
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= h || y < 0 || y >= w) ? true : false;
    }

    public static void setNode(int x, int y) {
        // 문인 경우, 해당 문을 열 수 있는 키가 없으면 별도 리스트에 담아두었다가 향후 열쇠를 얻는 경우 큐에 넣고 탐색
        char ch = String.valueOf(bd[x][y]).toLowerCase().charAt(0);
        if(bd[x][y] >= 'A' && bd[x][y] <= 'Z'
                // 최초에 키가 주어지지 않는 경우도 있으므로 size != 0 조건은 제거
                // && keys.size() != 0 && !keys.contains(ch)) {
                && !keys.contains(ch)) {
            doors[bd[x][y] - 'A'].add(new Node(x, y));
            return;
        }
        // 열쇠이면
        else if(bd[x][y] >= 'a' && bd[x][y] <= 'z') {
            keys.add(bd[x][y]);
        }
        // 문서이면
        else if(bd[x][y] == '$') {
            doc++;
        }

        q.offer(new Node(x, y));
        visited[x][y] = true;
    }
}

Feedback

최초에 문을 방문할 당시 해당 문을 열 수 있는 열쇠가 없었지만, 이후 빌딩을 돌면서 열쇠를 얻을 수 있는 경우가 존재한다. 이 경우 이전에 못열었던 문을 다시 열면서 탐색을 진행할 수 있어야 한다. 이 부분을 생각해내기는 하였지만, 구현에 어려움이 있어 구글링의 도움을 받았다..

열지 못한 문을 따로 저장해두기 위한 리스트형 배열을 선언하고, 매 탐색 진행 후 마다 이 리스트형 배열을 순회하며 새로 얻은 열쇠로 문을 열 수 있는지를 판단했다.