[BOJ/JavaScript] 9328: 열쇠

문제

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

2차원 좌표 상의 맵에서 문서를 훔치려고 한다.

문은 모두 잠겨 있고, 문을 열려면 열쇠가 필요하다.

열쇠의 일부를 미리 가지고 있고 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

상하좌우로만 이동할 수 있을 때, 훔칠 수 있는 문서의 최대 개수를 구하려고 한다.

• 테스트 케이스의 개수 ≤ 100
• 2 ≤  h, w ≤  100 

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

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

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

 

풀이

JS로 오랜만에 문제를 풀었더니 입력을 받는 코드가 기억이 안나 입력을 제대로 받는 방법부터 머리에 익혀야 할 것 같다. 아직은 Java만큼 익숙하지 않다. 자연스럽게 작성하려면 더 많은 연습이 필요할 것 같다.

💡 JS로 다수의 테스트 케이스 입력을 받을 땐 인덱스 변수를 사용하는 것이 좋다. 예를 들면 다음과 같이 작성할 수 있다.

const test = +input[0];
let line = 1;

for (let t = 0; t < test; t++) {
    const [h, w] = input[line++].split(" ").map(Number);
    const map = input.slice(line, line + h).map(line => line.split(""));
    line += h;
    const keys = input[line++];
    
    // ...
}

 

열쇠를 가진 상태를 유지하며 맵을 최단거리로 맵을 탐색해야 한다. 목표 좌표까지 최단거리로 탐색하기 위해서 BFS를 사용한다.

DFS로 풀 수도 있겠지만, 이 문제는 열쇠가 없어서 방문하지 못한 곳을 열쇠를 얻은 후 재방문해야 할 수 있으므로 방문한 좌표를 다시 방문하지 않는 일반적인 DFS 사용 방식과는 거리가 멀다.

 

이 문제의 핵심은 열쇠가 없어서 방문하지 못한 곳을 열쇠를 획득한 후, 재방문하게끔 해주는 것이 핵심이다.

이를 위해 `doors`라는 객체를 선언해두고 사용한다. `doors` 객체는 문의 형태를 키로, 그 좌표를 값으로 가지는 객체다.

일단 문을 방문했을 때, 열쇠가 없으면 문의 좌표를 저장해두고, 열쇠를 가지게 될 경우, 문의 좌표로 들어갈 수 있게 되며 탐색 가능한 좌표가 늘어나게 된다.

 

코드

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt", "utf8")
    .trim()
    .split("\n");

const test = +input[0];
let line = 1;
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

for (let t = 0; t < test; t++) {
    const [h, w] = input[line++].split(" ").map(Number);
    const map = input.slice(line, line + h).map(line => line.split(""));
    line += h;
    const keys = input[line++];
    const keySet = new Set(keys === "0" ? [] : keys.split(""));

    const docs = bfs(h, w, map, keySet);
    console.log(docs);
}

function bfs(h, w, map, keySet) {
    const visited = Array.from({ length : h }, () => Array(w).fill(false));
    const queue = [];
    const doors = {};
    let docs = 0;

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            if ((i === 0 || i === h - 1 || j === 0 || j === w - 1) 
                && map[i][j] !== "*") {
                queue.push([i, j]);
                visited[i][j] = true;        
            }
        }
    }
    
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        const cell = map[x][y]; 

        // 문서를 발견하면
        if (cell === "$") {
            docs++;
            map[x][y] = "."; // 중복 계산을 방지하기 위한 처리
        }

        // 열쇠를 발견 하면
        if ("a" <= cell && cell <= "z") {
            // 획득한 키인 경우,
            if (!keySet.has(cell)) {
                keySet.add(cell); // 키를 키셋에 담음
                // 열 수 있는 문이면 큐에 넣고 방문 처리
                const door = cell.toUpperCase();
                if (doors[door]) {
                    for (const [dx, dy] of doors[door]) {
                        queue.push([dx, dy]);
                        visited[dx][dy] = true;
                    }
                }
            }
        }

        // 문을 발견하면
        if ("A" <= cell && cell <= "Z") {
            // 키가 생기면 방문할 리스트에 추가
            if (!keySet.has(cell.toLowerCase())) {
                doors[cell] ??= [];
                doors[cell].push([x, y]);
                continue;
            }
        }

        for (let d = 0; d < 4; d++) {
            const nx = x + dx[d];
            const ny = y + dy[d];

            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (visited[nx][ny]) continue;
            if (map[nx][ny] === "*") continue;
            
            queue.push([nx, ny]);
            visited[nx][ny] = true;
        }
    }

    return docs;
}