[개발일지] - 95(개천절)

(1).백준 14502번 연구소는 바이러스가 퍼진 연구소에서 차단벽을 3개 세울 수 있을 때

안전지대를 최대한 몇칸 확보할 수 있는지를 묻는 문제였다.

 

처음에는 상당히 혼란스러웠지만 사이즈 제한 자체가 8x8까지 제한되는 것을 보고 

모든 경우의 수를 다 확인하라는 것을 알 수 있었고

사실 각각의 경우가 존재하는 경우 해당하는 사항의 결과값 도출은 간단했다.

 

하지만 모든 경우를 파악해서 넣는 부분이 살짝 당황스러웠는데

가능한 조건들을 모두 파악하고(0인 상태)

해당 값들을 모두 zeroArr이라는 곳에 담은 다음

index를 3개의 for문으로 조합 방식으로 접근해 결과값을 max와 비교해 해결했다.

const input = `7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0`.split('\n').map(el => el.split(' ').map(Number))
const [x, y] = input.shift()
const zeroArr = []
let max = 0

const dfs = (arr) => {
    const stack = []
    let count = 0
    for(let i = 0 ; i < arr.length ; i++){
        for(let j = 0 ; j < arr[0].length ; j++){
            if(arr[i][j] === 2){
                stack.push([i, j])
            }
        }
    }
    while (stack.length > 0) {
        const [x, y] = stack.pop()
        if(arr[x-1] && arr[x-1][y] === 0){
            arr[x-1][y] = 2
            stack.push([x-1, y])
        }
        if(arr[x+1] && arr[x+1][y] === 0){
            arr[x+1][y] = 2
            stack.push([x+1, y])
        }
        if(arr[x][y+1] === 0){
            arr[x][y+1] = 2
            stack.push([x, y+1])
        }
        if(arr[x][y-1] === 0){
            arr[x][y-1] = 2
            stack.push([x, y-1])
        }
    }

    for(let i = 0 ; i < x ; i++){
        for(let j = 0 ; j < y ; j++){
            if(arr[i][j] === 0){
                count++
            }
        }
    }
    return count
}

for(let i = 0 ; i < x ; i++){
    for(let j = 0 ; j < y ; j++){
        if(input[i][j] === 0){
            zeroArr.push([i,j])
        }
    }
}


for(let i = 0 ; i < zeroArr.length-2 ; i++){
    for(let j = i+1 ; j < zeroArr.length-1 ; j++){
        for(let k = j+1 ; k < zeroArr.length ; k++){
            const newArr = []
            for(let i = 0 ; i < x ; i++){
                newArr.push([...input[i]])
            }
            newArr[zeroArr[i][0]][zeroArr[i][1]] = 1
            newArr[zeroArr[j][0]][zeroArr[j][1]] = 1
            newArr[zeroArr[k][0]][zeroArr[k][1]] = 1
            max = Math.max(max, dfs(newArr))
        }
    }
}

console.log(max)