문제

상근씨가 빌딩에서 중요한 문서를 훔쳐야한다.. 평면도에는 문서, 문, 열쇠의 위치가 표시되어있고 이미 가지고 있는 열쇠도 있다.

• '.'는 빈 공간
• '*'은 벽
• '$'은 문서
• 알파벳 대문자는 문
• 알파벳 소문자는 열쇠
• 이미 가지고 있는 열쇠 (없으면 0)

풀이

처음에 진짜! 혼자 풀려고 했는데 진짜 모르겠어서 거의 컨닝해서 풀었음. 그럼에도 기록하는 이유는 다음에 제발 기억했다가 풀었으면 좋겠어서..

1. 상근이가 처음에 들어가는 것은 빌딩의 가장자리의 빈 공간 or 문을 통해 들어간다.
   이걸 위해 전체 평면도에서 각 가로+2, 세로+2를 해서 테두리 만든다.

5*5의 경우 예시 -> 7*7이 됨.
[1][1][1][1][1][1][1]
[1][0][0][0][0][0][1]
[1][0][0][0][0][0][1]
[1][0][0][0][0][0][1]
[1][0][0][0][0][0][1]
[1][0][0][0][0][0][1]
[1][1][1][1][1][1][1]

2. 필요한 자료구조

• map = new char[h + 2][w + 2] : 전체 평면도
• visited = new boolean[h + 2][w + 2] : 방문 체크
• key = new boolean[26] : 알파벳 소문자 키 저장 (있으면 true)
• gates = new ArrayList[26] : 방문했던 문 중에 열쇠가 없었던 문의 좌표 객체 저장. (나중에 그 열쇠를 얻었을 때 방문하기 위해)

3. BFS

• 상하좌우로 좌표를 변경시키면서 다음 좌표가 평면도 안에 존재하고, 벽이 아니면서 방문하지 않은 경우 탐색
• 이때 문, 열쇠, 문서, 빈 칸일 경우에 따라 실행 내용을 조금씩 달리해준다.
• 열쇠를 새로 얻은 경우 알파벳만큼 gates 배열을 순회하며 키가 없어 각 알파벳 문을 열지못한 경우중에 새로 얻은 키로 문을 열 수 있는 경우 Queue에 넣어준다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_9328 {
    static char[][] map;
    static boolean[] key; //알파벳 26개
    static ArrayList<Point>[] gates; // 열지 못한 문
    static boolean[][] visited;
    static int h;
    static int 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 tc = Integer.parseInt(br.readLine());

        for (int t = 0; t < tc; t++) {
            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[26];

            count = 0;

            /* 문 초기화 */
            for (int i = 0; i < 26; i++) {
                gates[i] = 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> q = new LinkedList<>();
        q.add(new Point(0, 0));
        visited[0][0] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.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' >= 0 && elem - 'A' <= 25) {
                    // 문 발견
                    if (key[elem - 'A']) {
                        map[nx][ny] = '.';
                        visited[nx][ny] = true;
                        q.add(new Point(nx, ny));
                    } else {
                        gates[elem - 'A'].add(new Point(nx, ny));
                    }
                } else if (elem - 'a' >= 0 && elem - 'a' <= 25) {
                    // 열쇠 발견
                    key[elem - 'a'] = true;
                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny));

                    for (int j = 0; j <= 25; j++) {
                        if (gates[j].size() != 0 && key[j]) {
                            for (int z = 0; z < gates[j].size(); z++) {
                                Point temp = gates[j].get(z);
                                map[temp.x][temp.y] = '.';
                                visited[temp.x][temp.y] = true;
                                q.add(new Point(temp.x, temp.y));
                            }
                        }
                    }
                } else if (elem == '$') {
                    // 문서 발견
                    count++;
                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny));
                } else {
                    // 빈 칸 '.'
                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny));
                }

            }
        }
    }

    static class Point {
        int x;
        int y;

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

}

후기

문을 먼저 방문하고, 나중에 열쇠를 얻은 케이스를 생각해내지 못했음
이런 거 스스로 생각하는 사람은 진짜 멋진 어른이다..