[백준 2630] 색종이 만들기 with Node.js

문제 링크

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

2630번: 색종이 만들기

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
const n = +input[0];
const paper = input.slice(1).map(v => v.split(" "));
const size = [128, 64, 32, 16, 8, 4, 2, 1].filter(v => v <= n);
let white = 0;
let blue = 0;
size.forEach(v => {
    for (let i=0; i<=n-v; i+=v) {
        for (let j=0; j<=n-v; j+=v) {
            let color = paper[i][j];
            let mono = true;
            outer : for (let x=i; x<i+v; x++) {
                for (let y=j; y<j+v; y++) {
                    if (paper[x][y] === "2" || paper[x][y] !== color) {
                        mono = false;
                        break outer;
                    }
                }
            }
            if (mono) {
                if (color === "0") white++;
                else if (color === "1") blue++;
                for (let x=i; x<i+v; x++) {
                    for (let y=j; y<j+v; y++) {
                        paper[x][y] = "2";
                    }
                }
            }
        }
    }
});
console.log(white);
console.log(blue);

예를 들어 n이 8이면 nxn크기의 사각형에서 8x8, 4x4, 2x2, 1x1만큼의 영역을 순회하며 해당 영역 내 색깔이 모두 동일한 색깔인지 확인하여 색종이의 개수를 센다. 이미 센 영역은 2로 바꾸어 놓고 해당 영역은 다음 순회때는 확인하지 않도록 하였다.

 

 

 

---

2021-07-07 풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input[0];
const paper = input.slice(1).map(v => v.split(" ").map(vv => +vv));
const countPaper = n => {
    const count = [0, 0];
    const recursion = (n, x, y) => {
        let total = 0;
        for(let i=0; i<n; i++) {
            for(let j=0; j<n; j++) {
                total += paper[y+j][x+i];
            }
        }
        if (total === 0) count[0]++;
        else if (total === n*n) count[1]++;
        else {
            n /= 2;
            recursion(n, x, y);
            recursion(n, x+n, y);
            recursion(n, x, y+n);
            recursion(n, x+n, y+n);
        }
    }
    recursion(n, 0, 0);
    console.log(count.join("\n"));
};
countPaper(n);

recursion에서 현재 종이의 모든 숫자를 더한 값이 0이면 흰색 개수를 증가시키고, n*n이면 파란색 개수를 증가시키고, 둘 다 아니라면 종이를 4분할 하여 각각의 종이별로 다시 recursion을 재귀호출하였다.

 

 

다른 언어로 된 풀이

[백준 2630] 색종이 만들기 with Python