[백준 1992] 쿼드트리 with Node.js

문제 링크

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

1992번: 쿼드트리

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input[0];
const screen = input.slice(1).map(v => v.split("").map(vv => +vv));

const genQuadTree = n => {
    const quadTree = [];
    const recursion = (n, x, y) => {
        let total = 0;
        for(let i=0; i<n; i++) {
            for(let j=0; j<n; j++) {
                total += screen[y+j][x+i];
            }
        }
        if (total === 0) quadTree.push("0");
        else if (total === n*n) quadTree.push("1");
        else {
            n /= 2;
            quadTree.push("(");
            recursion(n, x, y);
            recursion(n, x+n, y);
            recursion(n, x, y+n);
            recursion(n, x+n, y+n);
            quadTree.push(")");
        }
    }
    recursion(n, 0, 0);
    console.log(quadTree.join(""));
};

genQuadTree(n);

이 문제는 [백준 2630] 색종이 만들기 문제와 거의 동일한 문제다.

 

recursion에서 현재 화면이 모두 같은 색이면 현재 색깔을 quadTree에 추가하고, 그렇지 않으면 화면을 4분할하여 각각의 화면별로 재귀호출한다.

이 때, 괄호는 화면이 분할될 때에만 필요하므로, 화면 분할시 재귀호출 전에 여는 괄호를, 모든 재귀호출이 끝난 뒤 닫는 괄호를 quadTree에 추가한다.