[JavaScript/BFS] 백준 골드 5 : 18405 - 경쟁적 전염

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

18405번: 경쟁적 전염

---

작성한 코드 1 (완전탐색, 시간초과)

const [n, k] = input.shift().split(' ').map(Number);
const [s, x, y] = input.pop().split(' ').map(Number);
const board = input.map((i) => i.split(' ').map(Number));


const infection = (c,r, num) => {
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    for(let i=0;i<4;i++){
        const nx = c + dx[i];
        const ny = r + dy[i];

        if(nx >= 0 && nx < n && ny >=0 && ny <n) {
            if(board[nx][ny] === 0){
                board[nx][ny] = num;
            }
        }
    }

}

const solution = () => {
    for(let a=0;a<s;a++){
        for(let b=0;b<k;b++){
            const nums = [];
            for(let i=0;i<n;i++){
                for(let j=0;j<n;j++){
                    if(board[i][j] === b+1){
                        nums.push([i,j]);
                    }
                }
            }

            for(let i=0;i<nums.length;i++){
                infection(nums[i][0], nums[i][1], b+1);
            }
        }
    }
    console.log(board[x-1][y-1]);
}

solution();

- 문제 해결은 되지만 시간초과 발생 

---

작성한 코드 2(BFS, 통과) 

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, k] = input.shift().split(' ').map(Number);
const [s, x, y] = input.pop().split(' ').map(Number);
const board = input.map((i) => i.split(' ').map(Number));


const bfs = () => {
    const queue = [];
    for(let i=0;i<n;i++){
        for(let j=0;j<n;j++){
            if(board[i][j] != 0){
                queue.push([board[i][j],0,i,j]);
            }
        }
    }

    queue.sort((a,b)=> a[0]-b[0]);

    while(queue.length > 0){
        
        const [virus, time, x, y] = queue.shift();

        if(time === s) break;
        const dx = [-1, 1, 0, 0];
        const dy = [0, 0, -1, 1];
        
        for(let i=0;i<4;i++){
            const nx = x + dx[i];
            const ny = y + dy[i];

            if(nx >= 0 && nx < n && ny >=0 && ny <n) {
                if(board[nx][ny] === 0){
                    board[nx][ny] = virus;
                    queue.push([virus, time+1, nx, ny]);
                }
            }
        }
    }

    console.log(board[x-1][y-1]);

}

bfs();

📍 풀이 

- 이것이 코딩테스트다 책에 수록된 풀이를 참고

- 숫자가 작은 순서대로 증식되기 때문에 작은 순서대로 한번 순회하고 -> 그 다음 단계 전염으로 넘어가야함 -> 너비 우선탐색인 BFS 

- 숫자가 작은 순서대로 큐에 넣고 큐에서 하나씩 꺼내면서 상하좌우를 탐색하는 방식으로 전염시킴 

-> 맨 처음에 순서대로 정렬하면 다음에 큐에 들어오는 좌표는 자연스럽게 정렬된 순서로 들어옴 

 

1. 큐에 바이러스 저장하고 정렬하기 

- 시간을 같이 저장하는 이유는 일정 시간이 되면 전염을 끝내야하기 때문 

- [바이러스 번호, 시간, x, y] 순으로 큐에 저장해주기 

- 바이러스 번호 기준으로 정렬하기 

const queue = [];
    for(let i=0;i<n;i++){
        for(let j=0;j<n;j++){
            if(board[i][j] != 0){
                queue.push([board[i][j],0,i,j]);
            }
        }
    }

    queue.sort((a,b)=> a[0]-b[0]);

 

2. 반복하면서 바이러스 전염시키기 

- 시간이 s가 되면 끝내기 (0부터 시작했기 때문에 s가 되자마자 끝내야함, s초의 감염은 진행하면 안됨) 

- 상하좌우 탐색해서 전염 가능하면 큐에 넣어주고, 넣으면서 시간 +1 하기 

while(queue.length > 0){
        
        const [virus, time, x, y] = queue.shift();

        if(time === s) break;
        const dx = [-1, 1, 0, 0];
        const dy = [0, 0, -1, 1];
        
        for(let i=0;i<4;i++){
            const nx = x + dx[i];
            const ny = y + dy[i];

            if(nx >= 0 && nx < n && ny >=0 && ny <n) {
                if(board[nx][ny] === 0){
                    board[nx][ny] = virus;
                    queue.push([virus, time+1, nx, ny]);
                }
            }
        }
    }

 

3. 출력하기 

- 배열을 사용해서 인덱스가 0,0 부터 시작되는데 문제에서는 1,1부터 시작한다고 생각하고 주어졌기 때문에 1씩 빼줌

 console.log(board[x-1][y-1]);