🎲 백준 9328번 열쇠

📣 문제

🧸 정말 힘겹게 풀었다😂
🎨 참고

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const T = +input.shift();

const dir = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

const answer = [];
let i = 0;
for (let t = 0; t < T; t++) {
  const [H, W] = input[i].split(" ").map(Number);
  const map = [];
  map.push(new Array(W + 2).fill("."));
  for (let h = i + 1; h < i + 1 + H; h++) {
    map.push([".", ...input[h].split(""), "."]);
  }
  map.push(new Array(W + 2).fill("."));
  i += H + 1;
  let keys = new Set();
  if (input[i] !== "0") keys = new Set(input[i].split(""));
  const doorPositions = {};
  i++;

  const dfs = () => {
    const stack = [[0, 0]];
    const visited = Array.from(new Array(H + 2), () =>
      new Array(W + 2).fill(false)
    );
    visited[0][0] = true;
    let doc = 0;

    while (stack.length) {
      let [y, x] = stack.pop();
      if (map[y][x].match(new RegExp(/^[A-Z]/))) {
        if (doorPositions[map[y][x].toLowerCase()] === undefined)
          doorPositions[map[y][x].toLowerCase()] = [[y, x]];
        else doorPositions[map[y][x].toLowerCase()].push([y, x]);
        //열쇠 없음
        if (!keys.has(map[y][x].toLowerCase())) {
          continue;
        } else map[y][x] === ".";
      }
      //열쇠 줍기
      else if (map[y][x].match(new RegExp(/^[a-z]/))) {
        keys.add(map[y][x]);
        const matching = doorPositions[map[y][x]];
        //문 열어놓기
        while (matching !== undefined && matching.length) {
          const [dy, dx] = matching.pop();
          map[dy][dx] = ".";
          stack.push([dy, dx]);
        }
      }
      //문서 훔침
      else if (map[y][x] === "$") doc++;

      for (let d = 0; d < 4; d++) {
        const [nextY, nextX] = [y + dir[d][0], x + dir[d][1]];
        if (
          nextX >= W + 2 ||
          nextY >= H + 2 ||
          nextX < 0 ||
          nextY < 0 ||
          map[nextY][nextX] === "*" ||
          visited[nextY][nextX]
        )
          continue;

        visited[nextY][nextX] = true;
        stack.push([nextY, nextX]);
      }
    }

    return doc;
  };

  answer.push(dfs());
}

console.log(answer.join("\n"));