[재귀] 백준 1780번 - 종이의 개수

[1780] 종이의 개수

Baekjoon 문제 링크

오늘은 재귀를 사용하는 문제를 풀어보았다.

문제 설명

먼저 문제를 분석해보자.

우선 종이를 자르는 함수(재귀 함수)를 만들어야 하는데, 나는 cutPaper라는 이름으로 만들었다.
cutPaper 함수 안에서는 종이를 구성하는 숫자가 모두 동일한지 확인하여 아래와 같이 처리해줘야 한다.

• 종이가 모두 같은 수로 되어 있는 경우(same) : 종료 조건이다. 빈도수만 증가시킨 후 return한다.
• 같은 수로 되어 있지 않은 경우(!same): 현재의 색종이를 9분할 한 후(행 3등분, 열 3등분) 각각에 대해 다시 cutPaper 함수를 호출한다.

예시 분석

예시로 주어진 input과 output을 바탕으로 어떤 식으로 코드가 작동하는지 알아보자

아이디어

처음에는 입력으로 받은 paper 배열을 slice해서 9등분한 뒤, 각각을 재귀함수에 계속 넘겨줬었다. 그런데 이렇게 하니까 메모리도 많이 사용하고 실행 속도도 느려졌다.
-> 이를 해결하기 위해서 paper 배열을 잘라 9개의 새로운 배열을 만드는 코드를 제거하고 각 색종이의 시작 인덱스를 넘겨주는 코드로 수정하였다.

코드 설명

해결을 위한 코드:

const fs = require('fs');
const [n,...arr] = fs.readFileSync("./dev/stdin").toString().trim().split("\n");

const N = +n;
const paper = arr.map(v => v.split(' ').map(v => +v));

let answer = [0, 0, 0]; // answer[0]: -1의 빈도수 / answer[1]: 0의 빈도수 / answer[2]: 1의 빈도수

function cutPaper(rowStart, colStart, size) {
    const first = paper[rowStart][colStart];
    let isSame = true;

    // 색종이 안에 있는 모든 숫자가 같은지 확인
    for (let r = rowStart; r < rowStart + size; r++) {
        for (let c = colStart; c < colStart + size; c++) {
            if (first !== paper[r][c]) {
                isSame = false;
                break;
            }
        }
        if (!isSame) break;
    }

    if (isSame) {
        // 모든 요소가 같으면 해당 숫자 빈도수 증가
        answer[first + 1]++;
        return;
    } else {
        // 9개의 색종이로 나눠 재귀 호출
        const newSize = size / 3; // 새로운 사이즈는 1/3
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                cutPaper(rowStart + i * newSize, colStart + j * newSize, newSize);
            }
        }
    }
};

cutPaper(0, 0, N);
console.log(answer.join('\n'));