문제 링크
https://www.acmicpc.net/problem/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에 추가한다.
'연습장 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
[백준 1074] Z with Python (0) | 2021.07.08 |
---|---|
[백준 1780] 종이의 개수 with Node.js (0) | 2021.07.08 |
[백준 2630] 색종이 만들기 with Python (0) | 2021.07.07 |
[백준 10994] 별 찍기 - 19 with Python (0) | 2021.07.06 |
[백준 6603] 로또 with Python (0) | 2021.07.06 |