백준 - 1780번 종이의 개수

Park Inhye·2024년 4월 2일

코테 연습

목록 보기

33/37

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄
- 행렬의 크기 N
N개의 줄
- 행렬 데이터

제한조건

1 ≤ N ≤ 3^7, N은 3k 꼴

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예시

// NOTE: 입력
9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

// NOTE: 출력
10
12
11

해결

실버2 문제인데 왜 어렵지..?
그래서 다른 분의 답을 쌔볐다.

분할정복

전체 n ** 2의 행렬을 탐색
조건에 맞지 않으면 9분할하여 탐색
행렬의 크기가 1 x 1 이 될 때까지 반복

이 과정을 거치기 위해서는 재귀힘수를 사용해야 했다.

재귀함수

매개변수
- 행렬의 크기
- x 시작점
- y 시작점
변수
- 행렬의 기준
  - 분할된 행렬 첫번째 숫자
  - paper[startX][startY]
  - 행렬의 모든 숫자와 비교
- 탐색 진행률을 저장할 숫자
행렬 완전 탐색
- 행렬값 == paper[startX][startY]인 경우
  - 탐색 진행률 + 1
- 행렬값 != paper[startX][startY]인 경우
  - break;
탐색 진행률에 따라 다르게 처리
- (탐색 진행률) == (행렬 크기 ** 2)인 경우
  - 행렬 내부 숫자는 모두 동일함
  - 해당 숫자의 count 값 + 1
- (탐색 진행률) != (행렬 크기 ** 2)인 경우
  - 다른 숫자가 섞여있음
  - 재귀함수 실행
  - 행렬의 크기, 시작위치 조정

전체 코드

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

const N = +n;
const _paper = inputs.map(v => v.split(' ').map(v => +v));

const countPaper = (n) => {
    const _count = [0, 0, 0];
    
    const divideArr = (matrixSize, startX, startY) => {
        // NOTE: 행렬의 기준
        const _baseNum = _paper[startX][startY];
      
        // NOTE: 탐색 진행률
        let _progressCount = 0;

        // NOTE: 행렬 완전탐색
        for (let i = 0; i < matrixSize; i++) {
            for (let j = 0; j < matrixSize; j++) {
                if (_paper[startX + i][startY + j] == _baseNum) _progressCount += 1;
                else break;
            }
        }
        
        if (_progressCount == matrixSize ** 2) {
            // NOTE: 모든 숫자가 동일
            _count[_baseNum + 1] += 1;
        } else {
            // NOTE: 다른 숫자가 섞임
            matrixSize /= 3;
            
            for (let i = 0; i < 3; i++) {
                for (let j = 0; j < 3; j++) {
                    divideArr(matrixSize, startX + matrixSize * i, startY + matrixSize * j);
                }
            }
        }
    }
    
    divideArr(n, 0, 0, _count);
    console.log(_count.join('\n'))
}

countPaper(N);