[JavaScript/node.js] 백준 24513번 - 좀비 바이러스

[문제]

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

24513번: 좀비 바이러스

 

[풀이]

BFS를 통해 바이러스를 퍼트립니다.

 

초기 세팅

• village : 마을 정보 저장
• virus: [x좌표, y좌표, 바이러스 타입] 형태로 바이러스 정보 저장
• checkOut(x, y) : 마을을 벗어난 위치면 true, 마을 안에 있다면 false를 반환

풀이 과정

bfs를 통해 갱신되는 바이러스 정보를 virus에 저장하며 모두 검사합니다.

 

이때 주의할 점은 동시간대에 1번 바이러스와 2번 바이러스가 만나면 3번 바이러스가 되는 것입니다.

따라서 아래와 같이 이전 바이러스 타입에서 +2씩 숫자를 더해주어 시간을 구분하였습니다.

• 첫번째 시간에 퍼진 바이러스 : 1, 2
• 두번째 시간에 퍼진 바이러스 : 3, 4
• 세번째 시간에 퍼진 바이러스 : 5, 6

(편의성을 위해 3번 바이러스로 번진 마을은 Infinity를 저장하여 구분)

 

bfs의 동작과정은 다음과 같습니다.

 

1. 만약 village가 -1이나 Infinity라면 더이상 바이러스가 퍼질 수 없으므로 continue합니다.

 

2. 상하좌우 방향으로 바이러스가 퍼질 수 있는지 검사합니다.

• village가 0이면 아직 바이러스가 퍼지지 않았으므로 이전 바이러스의 type + 2를 저장후  virus에 해당 정보를 push
• village와 새로 들어온 바이러스의 type이 다른 경우(짝, 홀 쌍일때) 에만 바이러스 3이 될 수 있는지 검사합니다.
  • village가 홀수면 (village의 숫자 - 1) === (type + 2) 인 경우에 바이러스 3으로 갱신 
  • village가 짝수면 (village의 숫자 + 1) === (type + 2) 인 경우에 바이러스 3으로 갱신

 

마지막으로 마을 정보를 모두 탐색하며 바이러스 1, 2, 3의 개수를 더합니다.

• -1이나 0이면 바이러스가 없음
• 홀수면 1번 바이러스
• 짝수면 2번 바이러스
• Infinity면 3번 바이러스

 

 

[코드]

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().split('\n');

const [N, M] = input[0].split(" ").map(Number);

// 마을 정보
const village = [];
// 바이러스 위치
let virus = [];

for (let i = 1; i <= N; i++) {
    village.push(input[i].split(" ").map(Number));
    for (let j = 0; j < M; j++) {
        if (village[i - 1][j] === 1 || village[i - 1][j] === 2) {
            // x, y, type
            virus.push([i - 1, j, village[i - 1][j]]);
        }
    }
}

const checkOut = (x, y) => {
    if (x < 0 || y < 0 || x >= N || y >= M) {
        return true;
    }
    return false;
}

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

let idx = 0;
let time = 2;

// 동시간대를 확인해야함!!
// 바이러스가 모두 퍼짐
while (idx < virus.length) {
    const [x, y, type] = virus[idx];
    idx++;
    if(village[x][y] === -1 || village[x][y] === Infinity) {
        continue;
    }
    for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (checkOut(nx, ny) || village[nx][ny] === -1 || village[nx][ny] === Infinity) {
            continue;
        }
        if(village[nx][ny] === 0) {
            // 첫 방문
            village[nx][ny] = type + 2;
            virus.push([nx, ny, type + 2]);
        } else {
            // 동시간대 다른 바이러스 방문
            if(type%2 !== village[nx][ny]%2) {
                // 바이러스 1이 들어옴
                if(type%2 === 1 && village[nx][ny] - 1 === type + 2) {
                    village[nx][ny] = Infinity;
                } else if(type%2 === 0 && village[nx][ny] + 1 === type + 2) {
                    village[nx][ny] = Infinity;
                }
            }
        }
    }
}

let one = 0;
let two = 0;
let three = 0;

for(let i=0;i<N;i++) {
    for(let j=0;j<M;j++) {
        if(village[i][j] === -1 || village[i][j] === 0) {
            continue;
        }
        if(village[i][j] %2 === 1) one++;
        else if(village[i][j] % 2 === 0) two++;
        else if(village[i][j] === Infinity) three++;
    }
}

console.log(one, two, three);