백준 14502번: 연구소 (javascript, DFS)

간단하고 전형적인 DFS문제이다. 

 

0은 빈칸이고 1이 벽, 2는 바이러스가 있는 곳이다. 최대 개수를 세야하므로 조합 혹은 완전탐색을 이용한 방법과 DP를 이용한 방법중에 선택해야 하는데 제한시간이 2초로 매우 넉넉하여 조합을 통한 모든 경우의 수를 비교 후 최대값을 찾는 알고리즘으로 풀었다.

 

이때 각각의 배열들(연구소)은 참조형 변수이기에 깊은 복사를 이용해서 불러와야 하는데 나는 배열의 각 행마다 전개구문을 사용함으로써 깊은 복사를 행하였다. 

 

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [ROW, COLUMN] = input[0].split(' ').map(a => Number(a))

function combination(arr, num){
    const res = [];
    if(num === 1) return arr.map((v) => [v]);

    arr.forEach((v, idx, arr) => {
        const rest = arr.slice(idx+1);
        const combinations = combination(rest, num-1);
        const attach = combinations.map((combination) => [v, ...combination]);
        res.push(...attach);
    })
    return res;
}

// DFS 함수 정의
const dx = [0, 0, 1, -1]
const dy = [1, -1, 0, 0]
function dfs(row,col){
    board[row][col] = 2
    for (let i=0; i<4; i++){
        const nrow = row + dx[i]
        const ncol = col + dy[i]
        if(0 <= ncol && ncol < COLUMN && 0 <= nrow && nrow < ROW && board[nrow][ncol] === 0){
            dfs(nrow, ncol)
        }
    }
}

let boards = new Array(ROW)
const empty_board = []

for(let i=0; i<ROW; i++){
    boards[i] = input[i+1].split(' ').map(a => Number(a))
    for(let j=0; j< COLUMN; j++){
        if (boards[i][j] === 0) {
            empty_board.push([i,j])
        }
    }
}
// 3군데 벽세울 수 있는 리스트
const candidates = combination(empty_board,3)
let answer = Number.NEGATIVE_INFINITY

for (const candidate of candidates){
    let cash = 0
    board = []
    for (let r = 0; r < ROW; r++){
        board[r] = [...boards[r]]
    }

    for (const candi of candidate){
        board[candi[0]][candi[1]] = 1
    }

    for (let row=0; row< ROW; row++){
        for (let col=0; col<COLUMN; col++){
            if(board[row][col] === 2) dfs(row,col)
        }
    }
    for(let row = 0; row< ROW; row++){
        cash += board[row].filter(a => a===0).length
    }
    if(cash>answer){
        answer = cash
    }
}

console.log(answer)