[BaekJoon] 9328번 - 열쇠 [Java][C++]

문제 링크

---

1. 아이디어

1층 빌딩의 정보가 주어져 있을 때 훔쳐올 수 있는 문서의 최대 개수를 구하는 문제다. BFS를 활용하면 해결할 수 있는데 먼저 빌딩 외부에서 빌딩의 경계 중 통과할 수 있는 곳을 통해 진입한다는 점에서 빌딩 외부에 빈 공간으로 이루어진 패딩을 한 칸 주고 $(0, 0)$ 에서 탐색을 시작해서 시작점을 찾는 로직을 간소화했다.

BFS의 경우 노드들을 담는 큐와 별도로 현재 열쇠가 없어서 열 수 없는 문을 담는 자료구조를 두었다. BFS 탐색 중 열쇠를 발견하면 해당 열쇠로 열 수 있는 문들을 큐로 옮겨서 탐색을 진행해주면 된다.

탐색은 방문하지 않았으면서 벽이 아니면 문이거나 열쇠가 있거나 문서가 있거나 빈 공간이거나 4가지 경우 중 하나인데 문일 경우 현재 열 수 없으면 별도의 자료구조에, 열 수 있으면 방문하고, 열쇠의 경우 방문하며 열쇠 정보를 갱신하고 해당 열쇠로 열 수 있는 문들을 큐로 옮겨주었다. 빈 공간이나 문서면 일단 방문하고 방문한 노드를 큐에서 꺼낼 때 문서면 개수를 세줬다.

현재 열쇠가 없어서 열 수 없는 문은 열쇠의 종류가 26가지이므로 큐 배열을 활용해서 효율적으로 처리해줬다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int n, m;
    static char[][] grid;

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

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            n = 1 + h + 1;
            m = 1 + w + 1;

            grid = new char[n][m];
            for (int i = 0; i < n; i++) {
                grid[i][0] = grid[i][m - 1] = '.';
            }
            for (int j = 0; j < m; j++) {
                grid[0][j] = grid[n - 1][j] = '.';
            }

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

            boolean[] hasKey = new boolean[26];

            String s = br.readLine();
            if (!s.equals("0")) {
                for (char c : s.toCharArray()) {
                    hasKey[c - 'a'] = true;
                }
            }

            sb.append(bfs(hasKey)).append("\n");
        }

        System.out.println(sb);
    }

    static boolean isKey(char c) {
        return 'a' <= c && c <= 'z';
    }

    static boolean isDoor(char c) {
        return 'A' <= c && c <= 'Z';
    }

    static int bfs(boolean[] hasKey) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});

        Queue<int[]>[] doors = new ArrayDeque[26];
        for (int i = 0; i < 26; i++) {
            doors[i] = new ArrayDeque<>();
        }

        boolean[][] vis = new boolean[n][m];
        vis[0][0] = true;

        int cnt = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (grid[cur[0]][cur[1]] == '$') cnt++;

            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (grid[nr][nc] == '*' || vis[nr][nc]) continue;

                if (isDoor(grid[nr][nc])) {
                    if (!hasKey[grid[nr][nc] - 'A']) {
                        doors[grid[nr][nc] - 'A'].offer(new int[]{nr, nc});
                        continue;
                    }
                }

                if (isKey(grid[nr][nc])) {
                    hasKey[grid[nr][nc] - 'a'] = true;
                    q.addAll(doors[grid[nr][nc] - 'a']);
                }

                q.offer(new int[]{nr, nc});
                vis[nr][nc] = true;
            }
        }

        return cnt;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
char grid[102][102];
bool vis[102][102];
bool hasKey[26];

int bfs(int n, int m) {
    queue<pair<int, int>> q;
    q.push({0, 0});

    vector<queue<pair<int, int>>> doors(26);

    vis[0][0] = true;

    int cnt = 0;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (grid[r][c] == '$') cnt++;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc] == '*' || vis[nr][nc]) continue;

            if ('A' <= grid[nr][nc] && grid[nr][nc] <= 'Z') {
                if (!hasKey[grid[nr][nc] - 'A']) {
                    doors[grid[nr][nc] - 'A'].push({nr, nc});
                    continue;
                }
            }

            if ('a' <= grid[nr][nc] && grid[nr][nc] <= 'z') {
                hasKey[grid[nr][nc] - 'a'] = true;
                while (!doors[grid[nr][nc] - 'a'].empty()) {
                    q.push(doors[grid[nr][nc] - 'a'].front());
                    doors[grid[nr][nc] - 'a'].pop();
                }
            }

            q.push({nr, nc});
            vis[nr][nc] = true;
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int h, w;
        cin >> h >> w;

        int n = h + 2;
        int m = w + 2;

        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            grid[i][0] = grid[i][m - 1] = '.';
        }
        for (int j = 0; j < m; j++) {
            grid[0][j] = grid[n - 1][j] = '.';
        }

        for (int i = 1; i <= h; i++) {
            string s;
            cin >> s;

            for (int j = 1; j <= w; j++) {
                grid[i][j] = s[j - 1];
            }
        }

        string s;
        cin >> s;

        memset(hasKey, 0, sizeof(hasKey));
        if (!(s == "0")) {
            for (char c : s) {
                hasKey[c - 'a'] = true;
            }
        }

        cout << bfs(n, m) << '\n';
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---