[JavaScript/재귀] 백준 실버 2 : 1980 - 종이의 개수

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

1780번: 종이의 개수

---

작성한 코드

// 1780
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input.shift(), 10);
const paper = input.map((row) => row.split(" ").map(Number));
const answer = [0, 0, 0];

const recursion = (x, y, size) => {
    const target = paper[x][y];
    let flag = true;

    for (let i = x; i < x + size; i++) {
        for (let j = y; j < y + size; j++) {
            if (paper[i][j] !== target) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
    }

    if (flag) {
        answer[target + 1]++;
    } else {
        const newSize = size / 3;
        recursion(x, y, newSize);
        recursion(x + newSize, y, newSize);
        recursion(x + 2 * newSize, y, newSize);
        recursion(x, y + newSize, newSize);
        recursion(x + newSize, y + newSize, newSize);
        recursion(x + 2 * newSize, y + newSize, newSize);
        recursion(x, y + 2 * newSize, newSize);
        recursion(x + newSize, y + 2 * newSize, newSize);
        recursion(x + 2 * newSize, y + 2 * newSize, newSize);
    }
};

recursion(0, 0, N);
console.log(answer.join("\n"));

 

📌 풀이 

(1) 해당 구역이 전부 같은 숫자로 이루어져 있는지 확인한다.

해당 구역 내의 숫자 하나를 target으로 설정해서 배열 내 모든 숫자가 target과 일치하는지 확인한다. 그리고 일치하지 않다면 flag를 변경한다.

const target = paper[x][y];
let flag = true;

for (let i = x; i < x + size; i++) {
    for (let j = y; j < y + size; j++) {
        if (paper[i][j] !== target) { // 확인하기
            flag = false;
            break;
        }
    }
    if (!flag) break;
}

(2) 만약 해당 구역이 전부 같은 숫자가 아니라면 9등분하고, 각 9개의 구역에서 (1)의 과정을 반복한다.

9등분이니까 현재 크기를 3으로 나누면 9등분한 값의 크기가 될 수 있다. x,y는 9등분 했을 시 시작점으로 설정해서 다시 재귀함수를 실행한다.

if (flag) {
        answer[target + 1]++;
    } else {
        const newSize = size / 3;
        recursion(x, y, newSize);
        recursion(x + newSize, y, newSize);
        recursion(x + 2 * newSize, y, newSize);
        recursion(x, y + newSize, newSize);
        recursion(x + newSize, y + newSize, newSize);
        recursion(x + 2 * newSize, y + newSize, newSize);
        recursion(x, y + 2 * newSize, newSize);
        recursion(x + newSize, y + 2 * newSize, newSize);
        recursion(x + 2 * newSize, y + 2 * newSize, newSize);
    }

 

 

📌 참고

https://velog.io/@arthur/1780.-%EC%A2%85%EC%9D%B4%EC%9D%98-%EA%B0%9C%EC%88%98-node.js-javascript

1780. 종이의 개수 - node.js / javascript

✅ 성공