[백준] 18405. 경쟁적 전염

문제 링크

[백준] 18405. 경쟁적 전염

풀이 과정

BFS 탐색 문제입니다.

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (!map[i][j]) continue;
        if (!virus[map[i][j]]) virus[map[i][j]] = [];

        visit[i][j] = true;
        virus[map[i][j]].push({ x: i, y: j });
    }
}

먼저 맵을 입력받습니다. 로직은 다음과 같습니다.

1. 바이러스가 존재하지 않으면, 아래 과정을 생략합니다.
2. 바이러스가 존재하면, 먼저 해당 바이러스 번호를 인덱스로 하는 virus 배열 요소가 null인지 확인하고, 널이면 새로운 빈 배열을 할당해줍니다.
3. 해당 좌표를 방문처리 한 후에, 바이러스 배열 요소에 추가해줍니다.

virus 는 2차원 배열로 존재하고, 그 요소는 해당 번호를 인덱스로 갖는 바이러스 번호가 맵에 없는 경우에는 null이 됩니다.

for (let s = 0; s < S; s++) {
    for (let v = 1; v <= K; v++) {
        let tmp = [];

        while (virus[v]?.length) {
            let now = virus[v].shift();

            for (let d = 0; d < 4; d++) {
                let nx = now.x + dx[d],
                    ny = now.y + dy[d];

                if (!inRange(nx, ny)) continue;

                if (!visit[nx][ny] && !map[nx][ny]) {
                    visit[nx][ny] = true;
                    map[nx][ny] = v;
                    tmp.push({ x: nx, y: ny });
                }
            }
        }

        virus[v] = tmp;
    }
}

시간 S초 동안 BFS 탐색을 진행합니다.

• 바이러스 번호 1부터 K까지, 적은 번호부터 맵을 채워나갑니다.
• virus[v] 를 큐로 여기고, 길이가 0이될 때까지 번호 v를 갖는 모든 바이러스들을 큐에서 뽑아 이동시킵니다. 이 때, 이동된 새로운 좌표를 tmp 배열에 임시 저장한 후, 탐색이 종료되면 주소값을 virus[v]에 옮겨줍니다. virus[v]에는 다음 번에 이동시켜야할 바이러스가 새롭게 담기게 됩니다.
• virus[v] 가 위에서 봤듯이 null일 수 있기 때문에, while 문의 조건문에 옵셔널 체이닝을 적용한 모습을 볼 수 있습니다.

코드

const fs = require("fs");
const stdin = (
    process.platform === "linux"
        ? fs.readFileSync("/dev/stdin")
        : `3 3
1 0 2
0 0 0
3 0 0
2 3 2`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const [N, K] = input().split(" ").map(Number);
const map = Array.from(Array(N), () => Array(N).fill(0));
for (let i = 0; i < N; i++) map[i] = input().split(" ").map(Number);
const visit = Array.from(Array(N), () => Array(N).fill(false));
const [S, X, Y] = input().split(" ").map(Number);
const virus = Array(K + 1);
const dx = [-1, 1, 0, 0],
    dy = [0, 0, -1, 1];

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (!map[i][j]) continue;
        if (!virus[map[i][j]]) virus[map[i][j]] = [];

        visit[i][j] = true;
        virus[map[i][j]].push({ x: i, y: j });
    }
}

for (let s = 0; s < S; s++) {
    for (let v = 1; v <= K; v++) {
        let tmp = [];

        while (virus[v]?.length) {
            let now = virus[v].shift();

            for (let d = 0; d < 4; d++) {
                let nx = now.x + dx[d],
                    ny = now.y + dy[d];

                if (!inRange(nx, ny)) continue;

                if (!visit[nx][ny] && !map[nx][ny]) {
                    visit[nx][ny] = true;
                    map[nx][ny] = v;
                    tmp.push({ x: nx, y: ny });
                }
            }
        }

        virus[v] = tmp;
    }
}

console.log(map[X - 1][Y - 1]);

function inRange(x, y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}