11967 불 켜기 (자바스크립트)

문제

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

========

문제 분석

(0,0) 부터 시작하여 불이 켜진 곳만을 탐색 할 수 있는 문제이다.

1. 현재 지점에서 킬 수 있는 모든 좌표의 불을 킨다.

2. 그 지점에서부터 불을 켜져 있는 곳만을 전체 탐색을 시작한다.

3. 이때 전체 탐색을 진행하면서 해당 스테이지에서 방문 했던 곳은 재방문하지 않아야 한다.

4. 또한 처음 방문하는 곳이라면, 그곳과 연결 된 곳들의 불을 모두 켜줘야 한다. 이것을 위해 visited가 -1 이라면 큐에 담아둔다.

5. 처음 불을 킨 좌표에서의 탐색이 끝났다면 큐에서 다시 하나를 뽑아서, 그 지점의 불을 키고 탐색을 다시 돌리는 1번~4번의 과정을 반복한다. 

const lightGraph = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => false)
    );
const connectInfo = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => [])
);
const visited = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => -1)
);

lightGraph는 불이 켜진 곳을 알기 위한 그래프

connectInfo는 각 좌표에서 불을 킬 수 있는 좌표의 정보를 담을 그래프이다

visited는 방문 stage를 기록하는 것으로 각 스테이지 별로 탐색할 때 중복을 피하기 위한 그래프이다.

for (let i = 1; i < input.length; i++) {
    const [sx, sy, ex, ey] = input[i].split(' ').map((v) => +v - 1);
    connectInfo[sx][sy].push([ex, ey]);
}

좌표 별로 불을 킬 수 있는 좌표들을 담는 과정이다.

const q = [[0, 0]];
visited[0][0] = 0;
lightGraph[0][0] = true;

출발 지점은 0,0 이므로 위와 같이 초기화 

const [x, y] = q.shift();
let sss = false;
while (connectInfo[x][y].length) {
    const [cx, cy] = connectInfo[x][y].shift();
    lightGraph[cx][cy] = true;
    sss = true;
}
if (!sss) continue;
const searchQ = [[x, y]];
visited[x][y] += 1;
let cnt = visited[x][y];

q 에서 하나를 pop 한 뒤 그 좌표들과 연결 된 곳들의 불을 모두 키는 과정이다. 

searchQ는 탐색을 시작할 좌표를 넣어준다. 

cnt는 현재 스테이지를 의미한다. 

while (searchQ.length) {
    const [cx, cy] = searchQ.shift();

    for (let i = 0; i < 4; i++) {
        const nx = cx + dx[i];
        const ny = cy + dy[i];

        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

        if (visited[nx][ny] === cnt) continue;
        if (lightGraph[nx][ny] === false) continue;

        if (visited[nx][ny] === -1) {
            q.push([nx, ny]);
        }
        visited[nx][ny] = cnt;
        searchQ.push([nx, ny]);
    }
}

불을 킨 위치에서부터 탐색을 시작하여 중복 탐색은 배제하면서 처음 방문한 곳이라면 추후에 불을 키는 작업을 위해 q에 담아준다.

정답 코드

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

const main = (input) => {
    const [n, _] = input[0].split(' ').map((v) => +v);
    const lightGraph = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => false)
    );
    const connectInfo = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => [])
    );
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => -1)
    );

    for (let i = 1; i < input.length; i++) {
        const [sx, sy, ex, ey] = input[i].split(' ').map((v) => +v - 1);
        connectInfo[sx][sy].push([ex, ey]);
    }
    const q = [[0, 0]];
    visited[0][0] = 0;
    lightGraph[0][0] = true;

    while (q.length) {
        const [x, y] = q.shift();
        let sss = false;
        while (connectInfo[x][y].length) {
            const [cx, cy] = connectInfo[x][y].shift();
            lightGraph[cx][cy] = true;
            sss = true;
        }
        if (!sss) continue;
        const searchQ = [[x, y]];
        visited[x][y] += 1;
        let cnt = visited[x][y];
        while (searchQ.length) {
            const [cx, cy] = searchQ.shift();

            for (let i = 0; i < 4; i++) {
                const nx = cx + dx[i];
                const ny = cy + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

                if (visited[nx][ny] === cnt) continue;
                if (lightGraph[nx][ny] === false) continue;

                if (visited[nx][ny] === -1) {
                    q.push([nx, ny]);
                }
                visited[nx][ny] = cnt;
                searchQ.push([nx, ny]);
            }
        }
    }
    let answer = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (lightGraph[i][j]) answer++;
        }
    }
    console.log(answer);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);