QUADTREE self review

[dakyommii]

QUADTREE self review

• 파일명: QUADTREE/dakyommii.cpp
• 수행시간: 8ms

1. 문제 해결 과정

• 1차 시도: 쿼드트리로 표현했을 때 같은 부모 & 같은 레벨 노드들에 한해 왼쪽에서부터 홀수번째 노드들과 짝수번째 노드들끼리 교환하고, 가장 하단의 자식부터 뒤집어서 부모 노드까지 뒤집으면 쿼드를 뒤집을 수 있다고 까지 생각했지만 트리구현에 초점을 잘못 맞춰서 실패했습니다.
• 2차 시도: 1차 시도에 이어 노드 연결에 집중했고, 배열로 노드 간 연결을 구현하여 for문으로 노드들을 교환해서 쿼드트리를 뒤집으려 했으나 1차 시도 때와 같은 접근 방식이라 실패했습니다.
• 3차 시도: 출력 결과가 뒤집은 텍스트이므로 안쪽부터 텍스트를 뒤집어 가는 것에 초점을 맞췄습니다.

2. 아이디어

1. 같은 부모 & 같은 레벨 노드들에 한해 왼쪽에서 부터 홀수번째 노드들, 짝수번째 노드들끼리 교환하면 뒤집은 쿼드트리를 구할 수 있습니다.
   1-1. 트리 형태로 구현했을 때 가장 높은 레벨에 있는 자식들부터 뒤집어 주어야 노드들이 꼬이지 않으므로 안쪽 쿼드부터 뒤집어가야 합니다.
2. x를 만나면 다시 쿼드를 4개로 쪼개서 픽셀 색을 판단해야하기 때문에, x를 만나면 다음 글자들은 x를 4개로 쪼갰을 때 1,2,3,4분면의 픽셀을 뜻합니다. 따라서 x를 만나면 계속 쪼개면서 가장 안쪽의 픽셀부터 판단하며 뒤집어갑니다.
   2-1. w, b를 만나면 해당 픽셀이 모두 w이거나 b이므로 그대로 return 합니다.
3. 재귀함수를 이용해 각 쿼드의 1,2,3,4분면을 파악하고, 사분면을 모두 판단하면 뒤집은 결과를 return 해주는 방식을 반복해 안쪽부터 바깥쪽까지 뒤집습니다.

3. 코드 설명

#include <iostream>
using namespace std;

string quard(string &str, int idx) {
    //문자열 한 글자씩 추출
    char s = str[idx];
    
    //w, b일 경우 그대로 return해줌
    if(s == 'w') return "w";
    if(s == 'b') return "b";

1. 재귀함수를 사용하므로 x를 계속 만나면 그 x노드에 대한 하위 쿼드트리를 먼저 반전하고, 바깥쪽으로 점점 반전해갑니다. (ex. 2사분면의 1사분면 처리를 하다가 x를 만나면 그 x 안쪽의 반전 처리를 먼저 끝냅니다. 그 후에 다시 복귀하여 마저 2사분면의 2사분면 순으로 이어서 처리합니다.)
2. 좌측 상단 ➡️ 우측상단 ➡️ 좌측 하단 ➡️ 좌측상단 순으로 문자열 검사를 합니다.
3. 문자열이 x면 다음 글자부터 하위 픽셀로서 1,2,3,4분면을 채워야하므로 index를 x 다음 글자로 조정합니다.
4. 우측상단, 좌측하단, 좌측상단 검사는 앞 단계 검사가 끝나야 시작할 수 있으므로 각각의 인덱스는 앞 단계의 문자열 길이로 조정합니다.
5. 쪼개진 쿼드의 1,2,3,4분면을 모두 검사하면 각 분면에 해당하는 문자열이 모두 추출되므로, 1-3분면, 2-4분면 문자열끼리 교환해 return 하면 문자열을 뒤집을 수 있습니다.

    //똑같은 문자열에 대해 검사 시작점만 달라지는 것이므로 문자열은 고정되고 idx만 달라짐
    //좌측 상단(1)
    idx += 1;   //x 다음부터 시작
    string lt = quard(str, idx);
    
    //우측 상단(2)
    idx += lt.length(); //lt 끝난 지점부터 시작
    string rt = quard(str, idx);
    
    //좌측 하단(3)
    idx += rt.length(); //rt 끝난 지점부터 시작
    string lb = quard(str, idx);
    
    //우측 하단(4)
    idx += lb.length(); //lb 끝난 지점부터 시작
    string rb = quard(str, idx);
    
    return "x" + lb + rb + lt + rt;
   }

출력

문자열을 입력 받아 quard에 문자열을 전달하고, quard 뒤집기 연산을 합니다. 이때 연산을 처음 시작하는 것이므로 시작 index는 0으로 전달합니다.

int main() {
    //입력
    //케이스
    int C;
    cin >> C;
    
    //문자열
    string * s = new string[C];
    for (int i = 0; i < C; i++) {
        cin >> s[i];
    }
    
    //계산
    string * reverse = new string[C];
    for (int i = 0; i < C; i++) {
        reverse[i] = quard(s[i], 0);
    }
    
    //출력
    for (int i = 0; i < C; i++) {
        cout << reverse[i] << endl;
    }
}