[백준] 9328. 열쇠
문제 링크
풀이 과정
제출 시 틀렸던 이유
...
for (let i = 1; i <= H; i++) {
let s = input();
for (let j = 1; j <= W; j++) {
map[i][j] = s.charAt(j - 1);
// if (map[i][j] >= "A" && map[i][j] <= "Z") {
// let idx = (map[i][j] + "").charCodeAt(0) - "A".charCodeAt(0);
// if (!doors[idx]) doors[idx] = [];
// doors[idx].push({ x: i, y: j });
// }
}
}
...
처음부터 문들을 배열에 담았습니다. 도달하지도 않은 문을, 나중에 열쇠가 있다고 열어버린 후에 이동가능하다고 판단했으니 잘못된 답이 나오게 된 것 같습니다.
BFS 탐색 문제입니다. 아이디어는 다음과 같습니다.
- 빌딩 밖에서 안으로 접근할 수 있도록 둘레를 빈 공간(.)로 두른다.
- 문(A-Z)을 만나면, 다음과 같이 행동한다.
- 해당 문에 맞는 키가 없는 경우, 문까지 도달할 수 있었다는 것을 기억해 두기 위해 저장한다. 나중에 맞는 키를 얻게 되면, 저장되어 있던 모든 문들을 따서 이동할 수 있도록 하기 위함이다.
- 해당 문에 맞는 키가 있는 경우, 문을 따고 이동한다.
- 열쇠(a-z)를 만나면, 해당 열쇠로 열 수 있는 모든 문들을 열린 상태로 둔다. 여기서 말하는 “열린 상태로 둔다”는 의미는, 열쇠로 열 수 있는 모든 문들의 좌표를 큐에 넣어서, 추후에 문이 있는 위치부터 이동을 재개하도록 한다는 뜻이다.
let map = Array.from(Array(H + 2), () => Array(W + 2).fill("."));
let visit = Array.from(Array(H + 2), () => Array(W + 2).fill(false));
let doors = Array(26);
map과 visit 배열 모두 둘레를 빈 공간(.)으로 두르기 위해 행, 열을 2씩 추가했습니다. doors는 A-Z까지의 각 문의 좌표를 담아두기 위해 사용됩니다.
let keys = 0;
input()
.split("")
.filter((val) => val !== "0")
.forEach((val) => {
let idx = (val + "").charCodeAt(0) - "a".charCodeAt(0);
keys |= 1 << idx;
});
keys 는 초기 키의 정보와, BFS 탐색하면서 얻은 키의 정보를 포함합니다. 26개의 비트를 사용해, 각 알파벳을 인덱스로 하여 비트를 켭니다. 예를 들어, $10000_{(2)}$는 키 e를 갖고 있다는 것을 의미하며, $111_{(2)}$는 키 a, b, c를 갖고 있다는 것을 의미합니다.
let queue = [];
visit[0][0] = true;
queue.push({ x: 0, y: 0 });
좌표 (0, 0)을 방문처리 하고 큐에 넣어 BFS 탐색을 준비합니다.
while (queue.length) {
let now = queue.shift();
for (let d = 0; d < 4; d++) {
let nx = now.x + dx[d],
ny = now.y + dy[d];
if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] === "*") continue;
let next = map[nx][ny];
if (next === "$") {
answer++;
map[nx][ny] = ".";
} else if (next >= "A" && next <= "Z") {
let idx = (next + "").charCodeAt(0) - "A".charCodeAt(0);
if (!(keys & (1 << idx))) {
if (!doors[idx]) doors[idx] = [];
doors[idx].push({ x: nx, y: ny });
continue;
}
map[nx][ny] = ".";
} else if (next >= "a" && next <= "z") {
let idx = (next + "").charCodeAt(0) - "a".charCodeAt(0);
keys |= 1 << idx;
map[nx][ny] = ".";
while (doors[idx]?.length) queue.push(doors[idx].pop());
}
visit[nx][ny] = true;
queue.push({ x: nx, y: ny });
}
}
다음 좌표에 어떤 문자가 있느냐에 따라 처리가 달라집니다.
- 인덱스를 벗어나거나, 이미 방문을 했거나, 벽(*)이면 더이상 진행이 불가능하므로 큐에 넣는 작업을 생략합니다.
- 다음 문자가 문서($)인 경우, answer 를 증가시킵니다.
- 다음 문자가 문(A-Z)인 경우, 키가 없으면 doors 에 해당 좌표를 추가해주고, 키가 있다면 탐색을 계속 진행하기 위해 큐에 넣어줍니다.
- 다음 문자가 열쇠(a-z)인 경우, keys 에 해당 키를 추가해주고, 열릴 문이 있다면 큐에 각 문에 해당하는 좌표들을 추가해줍니다. 다음번에 꺼낼 때, 문을 시작으로 탐색이 계속됩니다.
코드
const fs = require("fs");
const stdin = (
process.platform === "linux"
? fs.readFileSync("/dev/stdin")
: `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`
)
.toString()
.trim()
.split("\n");
const input = (() => {
let line = 0;
return () => stdin[line++];
})();
const dx = [-1, 1, 0, 0],
dy = [0, 0, -1, 1];
const TC = +input();
let H, W;
let answer = 0;
for (let tc = 1; tc <= TC; tc++) {
[H, W] = input().split(" ").map(Number);
let map = Array.from(Array(H + 2), () => Array(W + 2).fill("."));
let visit = Array.from(Array(H + 2), () => Array(W + 2).fill(false));
let doors = Array(26);
answer = 0;
for (let i = 1; i <= H; i++) {
let s = input();
for (let j = 1; j <= W; j++) {
map[i][j] = s.charAt(j - 1);
}
}
let keys = 0;
input()
.split("")
.filter((val) => val !== "0")
.forEach((val) => {
let idx = (val + "").charCodeAt(0) - "a".charCodeAt(0);
keys |= 1 << idx;
});
let queue = [];
visit[0][0] = true;
queue.push({ x: 0, y: 0 });
while (queue.length) {
let now = queue.shift();
for (let d = 0; d < 4; d++) {
let nx = now.x + dx[d],
ny = now.y + dy[d];
if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] === "*") continue;
let next = map[nx][ny];
if (next === "$") {
answer++;
map[nx][ny] = ".";
} else if (next >= "A" && next <= "Z") {
let idx = (next + "").charCodeAt(0) - "A".charCodeAt(0);
if (!(keys & (1 << idx))) {
if (!doors[idx]) doors[idx] = [];
doors[idx].push({ x: nx, y: ny });
continue;
}
map[nx][ny] = ".";
} else if (next >= "a" && next <= "z") {
let idx = (next + "").charCodeAt(0) - "a".charCodeAt(0);
keys |= 1 << idx;
map[nx][ny] = ".";
while (doors[idx]?.length) queue.push(doors[idx].pop());
}
visit[nx][ny] = true;
queue.push({ x: nx, y: ny });
}
}
console.log(answer);
}
function inRange(x, y) {
return x >= 0 && x < H + 2 && y >= 0 && y < W + 2;
}
댓글남기기