[JavaScript/BFS] 백준 골드 2 : 11967 - 불켜기

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

11967번: 불켜기

---

📌 작성한 코드 

// 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;
}

 

✅ 성공

- 문제는 풀었지만 효율적인 풀이는 아니다..