쿼드트리 (백준 코딩테스트 1992번, DFS, NodeJS 풀이)

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

 

문제 수준:

실버1

 

 

문제 요약:

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리라는 방법이 있다.

주어진 영상이 모두 흰색이면 '0'을 출력하고, 모두 검은색이면 '1'을 출력한다.

주어진 영상이 흰색과 검은색이 섞여있으면, 화면을 4등분으로 나눠서 괄호 안에 좌상단, 우상단, 좌하단, 우하단 순서로 숫자를 기입한다.

자세한 예는 아래와 같다.

 

위의 그림에선 4x4 픽셀에 우측 상단에만 흰색이고 나머지 영역은 검은색이다. 이는 (0111)이라고 표현할 수 있다.

 

 

 

이런 경우에는 어떻게 표기할까? 좌상단을 기준으로 봤을때도 한 픽셀이 검은 영역이 되어 깔끔하게 흰색이 아닌 상황이다.

 

 

 

이럴땐 좌상단을 기운으로 또 한번 4분면을 나눠 괄호로 숫자를 만들어서 겹쳐 표기하면 된다.

그러므로 위의 경우는 ((0111)111)이 된다.

 

따라서 2의 제곱의 픽셀들이 주어지면 이를 계속 4분면으로 나눠 괄호로 묶은 숫자 표기를 만들어서 반환해주면 된다.

 

 

입출력 예 (입력 / 출력):

 

문제 풀이 전략:

재귀함수를 이용하여 풀 수 있는 문제이다.

1. 주어지는 입력값을 4분면으로 나눈다.

2. 4분면들이 순수 0이나 순수 1로 되어있는지, 아니면 혼재해 있는지 체크한다.

3. 순수 0이면 0을 반환, 순수 1이면 1을, 혼재해 있으면 해당 4분면을 기준으로 또 재귀함수를 실행(4분면으로 또 파고들기)한다.

4. 결국 4분면으로 나눴을 때 1픽셀씩 되어있는 경우가 쪼갤 수 있는 한계이므로 이를 기저조건으로 삼아 숫자를 반환한다.

 

 

내 풀이:

let [num, ...datas] = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");
// 첫번째 입력은 한 변의 길이, 나머지는 데이터이다.
let leng = Number(num); // 문자열을 숫자로 바꿔줌

function quard(leng, datas) { // 한 변의 길이와, 데이터를 인자로 받는 재귀함수
  if (leng === 1) { // 한 변의 길이가 1일때는
    return Number(datas); // 데이터가 0 또는 1이고 자기 자신이 답이다.
  }
  const divn = leng / 2; // 한 변을 2분의 1로 나눈다.

  //divn으로 4등분 한다.
  let leftUp = datas.slice(0, divn).map((x) => x.slice(0, divn)); // 좌상단
  let rightUp = datas.slice(0, divn).map((x) => x.slice(divn)); // 우상단
  let leftDown = datas.slice(divn).map((x) => x.slice(0, divn)); // 좌하단
  let rightDown = datas.slice(divn).map((x) => x.slice(divn)); // 우하단

  if (divn === 1) { //만약 divn이 1이라면 기저조건 실행
  // 이땐 픽셀이 딱 4개뿐이므로 0000이면 0을 반환, 1111이면 1을 반환, 나머지 1010...같은건 그대로 내보내면 된다.
    const v = Number(leftUp) + Number(rightUp) + Number(leftDown) + Number(rightDown); //총합 v가
    if (!v) { // 0인 경우는
      return 0; // 0 반환
    } else if (v === 4) { // 4인 경우는
      return 1; // 4개의 픽셀이 모두 1이란 말이므로 1 반환
    } else {
      return `(${datas.join("")})`; //그 외의 경우는 datas를 이어붙여서 반환
    }
  }

  const LUSUM = leftUp.join(""); // 좌상단의 픽셀들을 모두 이어붙여서 (00101000...)
  if (!LUSUM.includes("1")) { //1이 있는지 검사해서 1이 없다면
    leftUp = 0; // 좌상단은 0이다.
  } else if (!LUSUM.includes("0")) { // 0이 있는지 검사해서 0이 없다면
    leftUp = 1; // 좌상단은 1이다.
  } else { // 1과 0이 혼재되어 있다면
    leftUp = quard(divn, leftUp); //좌상단을 기준으로 재귀 실행
  }

  const RUSUM = rightUp.join(""); // 우상단의 픽셀들을 모두 이어붙여서 (00101000...)
  if (!RUSUM.includes("1")) { //1이 있는지 검사해서 1이 없다면
    rightUp = 0;  // 우상단은 0이다.
  } else if (!RUSUM.includes("0")) { // 0이 있는지 검사해서 0이 없다면
    rightUp = 1; // 우상단은 1이다.
  } else { // 1과 0이 혼재되어 있다면
    rightUp = quard(divn, rightUp); //우상단을 기준으로 재귀 실행
  }

  const LDSUM = leftDown.join(""); // 이하 좌하단과
  if (!LDSUM.includes(1)) {
    leftDown = 0;
  } else if (!LDSUM.includes(0)) {
    leftDown = 1;
  } else {
    leftDown = quard(divn, leftDown);
  }

  const RDSUM = rightDown.join(""); // 우하단도 동일하게 시행
  if (!RDSUM.includes(1)) {
    rightDown = 0;
  } else if (!RDSUM.includes(0)) {
    rightDown = 1;
  } else {
    rightDown = quard(divn, rightDown);
  }

  let sum = leftUp + leftDown + rightUp + rightDown; // 이렇게 나온 숫자들을 더해서
  // 순수 0이 나온다면 0 반환, 4가 4분면 모두 빽빽히 1이라는 소리이므로 1반환, 혼재되어 있다면 재대로 된 숫자가 안 나올테니 
  return sum === 0 ? 0 : sum === 4 ? 1 : `(${leftUp}${rightUp}${leftDown}${rightDown})`; //리터럴로 괄호 ()를 치고 그안에 좌상단,우상단,좌하단,우하단 순서로 기입.
}
console.log(quard(leng, datas)); // 재귀함수 실행

문제 푸는데도 한나절 썼고 디버깅하는데 시간이 1시간 정도 걸렸다..ㅠㅠ

재귀 자체는 잘 작동하고 기저조건에서 반환도 잘 일어났는데,

 

1. N 입력값이 1인 경우가 있는데 이를 대비 못했었다.

2. 기저조건에 (좌상단,우상단,좌하단,좌우단)을 써야됐는데 (좌상단,우상단,좌하단,좌하단) 이렇게 좌하단을 2개 써놓고 한참을 못 찾았다.