[JavaScript/재귀] 백준 실버 1: 1992 - 쿼드트리

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

1992번: 쿼드트리

---

📌 작성한 코드

// 1992
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 = Number(input.shift());
const video = input.map((row) => row.split("").map(Number));
let answer = "";

const recursion = (x, y, size) => {
    const target = video[x][y];
    let flag = true;
    for (let i = x; i < x + size; i++) {
        for (let j = y; j < y + size; j++) {
            if (video[i][j] !== target) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
    }

    if (flag) {
        answer += String(target);
    } else {
        const newSize = size / 2;

        answer += "(";
        recursion(x, y, newSize);
        recursion(x, y + newSize, newSize);
        recursion(x + newSize, y, newSize);
        recursion(x + newSize, y + newSize, newSize);
        answer += ")";
    }
};

recursion(0, 0, N);
console.log(answer);

 

📌 설명 

재귀를 통해서 코드를 압축하는 문제이다. 이전에 푼 종이의 개수, 색종이 만들기 문제와 매우 유사하다.

 

의사 코드를 작성해보면 이렇게 표현할 수 있다.

- 1. 확인하고자 하는 범위를 확인하여 한가지 색의 점으로 이루어져있는지 확인한다. 

- 2-1. 한가지 색으로 이루어져 있다면 해당 구역을 압축하여 하나의 숫자로 표현한다.

- 2-2. 한가지 색으로 이루어져 있지 않다면 해당 구역을 4등분 하여 다시 확인하기 시작한다.

const recursion = (x, y, size) => {
    const target = video[x][y];
    let flag = true;
    for (let i = x; i < x + size; i++) { // 1. 한가지 점으로 되어있는지 확인하기
        for (let j = y; j < y + size; j++) {
            if (video[i][j] !== target) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
    }

    if (flag) {
        answer += String(target); // 2-1. 한가지 점으로 되어있으면 해당 부분을 압축해서 표현하기
    } else {
        const newSize = size / 2; 

        answer += "(";
        recursion(x, y, newSize); // 2-2. 한가지 점으로 되어있지 않으면 해당 부분 4등분 해서 다시 확인하기
        recursion(x, y + newSize, newSize);
        recursion(x + newSize, y, newSize);
        recursion(x + newSize, y + newSize, newSize);
        answer += ")";
    }
};

 

주의해야 할 점 

1. 4개의 영역으로 나눈 경우에 해당 부분을 괄호로 묶어서 표현해야 하므로 재귀 실행 전, 후에 괄호를 답에 추가해줘야 한다.

2. 영상을 압축하는 순서는 (왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래) 이다. 재귀를 해당 순서대로 실행시켜줘야 한다.

 

✅ 성공