쿼드트리 압축

[hsskey]

쿼드트리 압축

N×N 크기의 흑백 영상(2차원 배열)을 쿼드트리 방식으로 압축

📝 제약조건

• N은 2의 제곱수 (1 ≤ N ≤ 64)
• 입력은 0 또는 1로만 구성
• 출력은 압축된 결과를 괄호로 표현

💡 예시

• Input:

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

• Output: ((1111)((1111)0000))

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 압축해보기

예시1) 2x2 영역
1 1
1 1
-> "(1)" (모두 1이므로 하나로 압축)

예시2) 2x2 영역
1 0
1 1
-> "(1011)" (섞여있어서 압축 불가)

Step 2: 접근 방법

• 직관적으로 생각하기

  1. 현재 영역이 모두 같은 숫자인지 확인
  2. 다른 숫자가 있다면 1/4로나누어 재귀적으로 처리
  3. 4개의 결과를 괄호로 묶어 반환

• 알고리즘 표 작성

현재 영역(li,lj,ri,rj) 확인
↓
모든 값이 같은지 체크
↓
같다 -> 해당 값을 문자열로 반환
↓
다르다 -> 영역을 4등분
↓
각 부분을 재귀적으로 처리
↓
4개의 결과를 괄호로 묶어 반환

Step 3: 코드 설계

1. 입력값 처리
   • N과 2차원 배열 입력받기
2. 재귀 함수 구현
   • 파라미터: 현재 영역의 좌표(li, lj, ri, rj)
   • 종료조건:
     1. 모든 값이 같을 때
     2. 영역 크기가 1x1일 때
   • 재귀단계:
     1. 영역을 4등분
     2. 각 부분을 재귀호출
     3. 결과를 괄호로 묶어 반환

Step 4: 코드 구현

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = Number(input[0])
const arr = []
for(let i = 1; i <= n; i++) {
    arr.push(input[i].split('').map(Number))
}

function fn(li, lj, ri, rj) {
    // 현재 영역의 첫 번째 값을 기준으로 검사
    const firstValue = arr[li][lj]
    let isConsistent = true

    // 모든 값이 같은지 확인
    for(let i = li; i < ri; i++) {
        for(let j = lj; j < rj; j++) {
            if(firstValue !== arr[i][j]) {
                isConsistent = false
                break
            }
        }
        if(!isConsistent) break
    }

    // 종료조건1: 모든 값이 같으면 압축
    if (isConsistent) return String(firstValue)        
    
    // 종료조건2: 1x1 영역이면 그대로 반환
    if(ri - li === 1) return String(firstValue)
     
    // 영역을 4등분하여 재귀호출
    const mi = Math.floor((li + ri) / 2)
    const mj = Math.floor((lj + rj) / 2)
    
    const rec1 = fn(li, lj, mi, mj)    // 왼쪽 위
    const rec2 = fn(li, mj, mi, rj)    // 오른쪽 위
    const rec3 = fn(mi, lj, ri, mj)    // 왼쪽 아래
    const rec4 = fn(mi, mj, ri, rj)    // 오른쪽 아래
    
    return `(${rec1}${rec2}${rec3}${rec4})`
}

const res = fn(0, 0, n, n)
console.log(res)