[Gold I] 열쇠 - 9328

문제 링크

성능 요약

메모리: 22796 KB, 시간: 196 ms

분류

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

문제 설명

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

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

입력

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

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

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

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

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 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

3
1
0

BFS를 반복하여 열쇠를 사용하는 경우를 탐색합니다.

H : 5

W : 17

• *: 벽

• .: 빈 공간

• a-z: 열쇠

• A-Z: 문

• $: 문서

얻은 열쇠 : { c, z }

1. 빌딩 밖에서 BFS탐색을 진행하여 최대한 열쇠와 문을 열어보고 열지 못한 문을 따로 저장합니다.

얻은 열쇠 : { c, p, z }

2. 닫힌 문에서 열쇠를 찾은 문이 없을 때까지 닫힌 문 기준 BFS탐색을 반복합니다.

닫힌 문 : { B, A, P, X, Y }

닫힌 문 : { B, A, X, Y }

닫힌 문 : { B, X, Y }

닫힌 문 : { B, Y }

더 이상 열쇠가 없어서 열 수 있는 문은 존재하지 않으므로 탐색 종료!

3. 탐색이 끝났을 때 문서를 훔치는 최대 개수를 결과로 출력합니다.

훔친 개수 : 3개 결과로 출력합니다.

아래의 텍스트 케이스도 통과해야합니다.

1
10 10
JEMOTOFJOY
VMISTuVMsV
THVIQLMNXZ
RIEVJUQTUT
RN$UGDEXWE
VESTQEMFgU
RCSiYMTTLC
LLdXTNJGXG
YRKBKSqIoD
RRDFPXMNHJ
l
result: 0
answer: 1

정답 코드(JAVA)

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

public class Main {
    static char[][] map;
    static boolean[] key; // 알파벳 26개
    static ArrayList<ArrayList<Point>> gates; // 열지 못한 문
    static boolean[][] visited;
    static int h, w;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < n; tc++) {
            String[] inputMap = br.readLine().split(" ");

            h = Integer.parseInt(inputMap[0]);
            w = Integer.parseInt(inputMap[1]);

            map = new char[h + 2][w + 2];
            visited = new boolean[h + 2][w + 2];
            key = new boolean[26];
            gates = new ArrayList<>();

            count = 0;

            // 문 초기화
            for (int i = 0; i < 26; i++) {
                gates.add(new ArrayList<>());
            }

            // 테두리 빈 칸으로 채우기
            for (int i = 0; i < h + 2; i++) {
                for (int j = 0; j < w + 2; j++) {
                    map[i][j] = '.';
                }
            }

            for (int i = 1; i <= h; i++) {
                String input = br.readLine();
                for (int j = 1; j <= w; j++) {
                    map[i][j] = input.charAt(j - 1);
                }
            }

            String keyInput = br.readLine();
            if (!keyInput.equals("0")) {
                for (int i = 0; i < keyInput.length(); i++) {
                    int temp = keyInput.charAt(i) - 'a';
                    key[temp] = true;
                }
            }

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

    static void bfs() {
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(0, 0));
        visited[0][0] = true;

        while (!que.isEmpty()) {
            Point cur = que.poll();

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

                if (nx < 0 || ny < 0 || nx >= h + 2 || ny >= w + 2) {
                    continue;
                }

                if (map[nx][ny] == '*' || visited[nx][ny]) {
                    continue;
                }

                int elem = map[nx][ny];
                if (elem >= 'A' && elem <= 'Z') {
                    // 문 발견
                    if (key[elem - 'A']) {
                        visited[nx][ny] = true;
                        que.add(new Point(nx, ny));
                    } else {
                        gates.get(elem - 'A').add(new Point(nx, ny));
                    }
                } else if (elem >= 'a' && elem <= 'z') {
                    // 열쇠 발견
                    key[elem - 'a'] = true;
                    visited[nx][ny] = true;
                    que.add(new Point(nx, ny));
  
                    for (Point temp : gates.get(elem - 'a')) {
                        if (!visited[temp.x][temp.y]) {
                            visited[temp.x][temp.y] = true;
                            que.add(temp);
                        }
                    }
                    gates.get(elem - 'a').clear(); // 처리한 문을 리스트에서 제거
                } else if (elem == '$') {
                    // 문서 발견
                    count++;
                    visited[nx][ny] = true;
                    que.add(new Point(nx, ny));
                } else {
                    // 빈 칸 '.'
                    visited[nx][ny] = true;
                    que.add(new Point(nx, ny));
                }
            }
        }
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}