색종이 만들기 (dfs)

 

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

2630번: 색종이 만들기

• 여러줄 입력 split('\n')
• map(e => Number(e)) === map(Number)
• 0항 0열부터 돌면서 isUnion을 검사한다
  • isUnion이거나 더이상 자를 수 없는 조각이면 왼쪽상단모서리가 1일떈 blue++, 0일땐 white++
  • !isUnion이면 한 변이 n/2크기로 잘라서 다시 isUnion검사를 한다

 

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

let [N, ...paper] = input;
paper = paper.map(p => p.split(' ').map(Number));
let white = 0;
let blue = 0;

function solution(r, c, n) {
    // 통일된 색이던가 색종이를 더이상 자를 수 없을 시
    if (isUnion(r, c, n) || n === 1) {
        if (paper[r][c] === 1) blue++;
        else white++;
        return;
    } 
    // 다른색이 섞이면 n/2씩 나눠서 다시 isUnion한지 검사
    const half = n/2;
    solution(r, c, half);
    solution(r+half, c, half);
    solution(r, c+half, half);
    solution(r+half, c+half, half);
}

function isUnion(r, c, n) {
    const first = paper[r][c];
    for (let i = r; i < r+n; i++) {
        for (let j = c; j < c+n; j++) {
            // 같은 색이 아님
            if (paper[i][j] !== first) return false;
        }
    }
    return true;
}

solution(0, 0, N);
console.log(`${white}\n${blue}`);