https://www.acmicpc.net/problem/11967
11967번: 불켜기
(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으
www.acmicpc.net
📌 작성한 코드
// 11967
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const buttons = input.map((str) => str.split(" ").map(Number));
const board = Array.from({ length: N + 1 }, () => Array.from({ length: N + 1 }, () => [false, 0]));
let visited = Array.from({ length: N + 1 }, () => Array(N + 1).fill(false));
const possible = Array.from({ length: N + 1 }, () => Array(N + 1).fill(false));
buttons.forEach(([x1, y1, x2, y2]) => {
if (board[x1][y1][1] === 0) board[x1][y1][1] = [[x2, y2]];
else board[x1][y1][1].push([x2, y2]);
});
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let count = 1;
const init = () => {
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= N; j++) {
visited[i][j] = false;
}
}
};
const bfs = (a, b) => {
let flag = false;
const queue = [];
queue.push([a, b]);
visited[a][b] = true;
board[a][b][0] = true;
let idx = 0;
while (queue.length > idx) {
const [x, y] = queue[idx++];
if (board[x][y][1] !== 0) {
board[x][y][1].forEach(([tx, ty]) => {
if (!board[tx][ty][0]) {
board[tx][ty][0] = true;
flag = true;
count++;
}
});
board[x][y][1] = 0;
}
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
if (board[nx][ny][0] === true && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
return flag;
};
while (true) {
const flag = bfs(1, 1);
init();
if (!flag) break;
}
console.log(count);
📌 설명
[문제 풀이시 주의해야 할 부분]
(1) 불이 켜진 곳으로만 이동할 수 있다.
(2) 방에 도달해야만 해당 방에 있는 스위치를 켤 수 있다.
(3) 이전에는 갈 수 없었던 방이, 스위치를 통해 불을 켜면서 나중에는 접근 가능해 질 수도 있다.
[문제 풀이 단계]
(1) 현재 도달한 방에서 켤 수 있는 스위치 켜기
- 스위치가 존재해야 하고, 스위치가 꺼져있는 상태에서만 스위치를 켤 수 있다. 스위치를 켠 이후에 count를 증가시킨다.
- 해당 방에 다시 도달 할 수 있으므로 스위치를 킨 이후에는 스위치를 초기화해서 다시 확인하지 않게 해준다.
if (board[x][y][1] !== 0) {
board[x][y][1].forEach(([tx, ty]) => {
if (!board[tx][ty][0]) {
board[tx][ty][0] = true;
flag = true;
count++;
}
});
board[x][y][1] = 0; // 스위티 초기화
}
(2) 맞닿은 방을 확인하면서 갈 수 있는지 확인하기
- 상하좌우로 맞닿은 방에 불이 켜져있고, 이전에 방문하지 않은 곳이면 방문하기 위해 큐에 추가한다.
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
if (board[nx][ny][0] === true && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
(3) 더이상 켤 수 있는 방이 없을 때까지 반복하기
- 주의해야 할 부분 (3)에서 말했듯, 추후에 불이 켜져서 방문 가능해지는 곳이 있을 수 있기에 1,1에서 bfs를 다시 시작한다.
- 만약 bfs를 다시 도는 동안 새로 불이 켜진 방이 없다면 그 때 반복문을 탈출한다.
while (true) {
const flag = bfs(1, 1);
init();
if (!flag) break;
}
✅ 성공
- 문제는 풀었지만 효율적인 풀이는 아니다..

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 골드 5 : 2011 - 암호 코드 (1) | 2024.02.26 |
|---|---|
| [JavaScript/DP] 백준 실버 1 : 4883 - 삼각 그래프 (0) | 2024.02.26 |
| [JavaScript] 백준 골드 4 : 3190 - 뱀 (0) | 2024.02.24 |
| [JavaScript/DFS] 백준 골드 3 : 9466 - 텀 프로젝트 (0) | 2024.02.22 |
| [JavaScript/DP] 백준 실버 1 : 11057 - 오르막수 (0) | 2024.02.20 |