백준[node.js] > 2630번 색종이 만들기

문제

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

 

문제풀이

분할정복 하는 문제이다. 재귀로 접근하여 쉽게 풀 수 있었다.

정사각형의 모든 색종이의 색이 같아야 하므로 큰 사각형부터 검사를 하고 검사하는 와중에 색종이 색이 다르면 4분할하여 다시 각 분할된 영역에서의 색종이 색이 같은지 확인하고 같으면 더 이상 분할하지 않고 해당 영역은 탐색을 끝낸다. 

위 과정을 코드로 풀면 아래와 같다. 

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

let N = Number(input.shift());

// 정사각 판을 2차원 배열 map으로 구현
let map = [];
for (let i = 0; i < input.length; ++i) {
    let line = input[i].split(" ").map((n) => Number(n));
    map.push(line);
}

let blue = 0;
let white = 0;

const recursive = (startR, startC, cnt) => {
    if (cnt === 1) {
        if (map[startR][startC] === 1) {
            blue++;
        } else {
            white++;
        }
        return;
    }

    let color = map[startR][startC];
    for (let i = startR; i < startR + cnt; ++i) {
        for (let j = startC; j < startC + cnt; ++j) {
            if (color !== map[i][j]) {
                let half = cnt / 2;
                recursive(startR, startC, half);
                recursive(startR + half, startC, half);
                recursive(startR, startC + half, half);
                recursive(startR + half, startC + half, half);
                return;
            }
        }
    }
    if (color === 1) {
        ++blue;
    } else {
        ++white;
    }
};

recursive(0, 0, N);

console.log(`${white}\n${blue}`);