알고스팟 문제 풀이 QUADTREE

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "QUADTREE"에 대한 풀이입니다.

목차

1. 문제 해결 전략
2. 코드 전문

QUADTREE 문제 URL은 다음과 같습니다.

• QUADTREE 문제

문제 해결 전략

제가 이 문제를 해결하기 위해서 체택한 방법은 "분할 정복"입니다. 보통 알고리즘 문제를 해결할 때는 "무식하게 풀기"를 적용한 이후, 문제를 최적화하기 위한 패러다임을 차차 적용하는 것이 좋습니다. 하지만, 위 문제에서는 "분할 정복"을 적용하라는 문구가 이미 적혀져 있습니다.

 

"주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, (이하 생략)"

 

4개로 분할해서 재귀적으로 표현한다. 이것은 4군데로 각기 나누어 문제를 해결하라는 소리와 일치합니다. 이것을 알고 간다면 문제는 굉장히 쉽게 해결할 수 있습니다. 문제의 조건을 충실히 따르면 되지요. 문제의 조건은 다음과 같습니다.

 

1. "w"라고 표현된 곳은 "w"로 표시합니다.
2. "b"라고 표현된 곳은 "b"로 표시합니다.
3. "x"라고 표현된 곳은 이후 4분면 왼쪽 위(lt), 오른쪽 위(rt), 왼쪽 아래(lb), 오른쪽 아래(rb)로 표현됩니다.
4. 안쪽의 쪼개지는 영역부터 가장 바깥쪽 영역까지 순서대로 상하를 반전합니다.

1, 2번 조건은 쉬우니 넘어갑시다. 3, 4번 조건들에 대해 살펴볼까요?. 만약 문제의 입력에서 "xbwwb"라고 해 봅시다. 그럼 4분면을 이렇게 나타낼 수 있습니다.

이를 4가지 영역으로 쪼개보면 처음 입력은 다음과 같이 나타낼 수 있습니다.

문자열로 표현하면 다음과 같아지겠죠?

 

"x" + "b"(lt) + "w"(rt) + "w"(lb) + "b"(rb)

 

이들을 상하 반전을 시켜보면 다음 그림과 같아집니다.

문자열로 표현하면 다음과 같습니다.

 

"x" + "w"(lb) + "b"(rb) + "b"(lt) + "w"(rt)

 

즉 상하 반전을 적용한다면, "xwbbw"로 바뀐다는 것이죠.

 

조금 더 복잡한 입력을 살펴볼까요? "xbwxbwwbb" 입력으로 들어왔다고 가정해봅시다. 그럼 그림으로 표현하면 다음과 같아지겠죠?

먼저 입력 문자열을 4개의 영역으로 나누면 다음과 같아집니다.

문자열로 표현하면 다음과 같아집니다.

 

"x" + "b"(lt) + "w"(rt) + "xbwwb"(lb) + "b"(rb)

 

왼쪽 아래 영역의 경우 또 4가지 영역으로 나뉘어집니다. 이를 그림으로 표현하면 다음과 같습니다.

왼쪽 아래 영역을 문자열로 표현하면 다음과 같아집니다.

 

"x" + "b"(lb-lt) + "w"(lb-rt) + "w"(lb-lb) + "b"(lb-rb)

 

쿼드 트리는 4개의 영역을 나누어 재귀적으로 호출되는 구조입니다. 즉, 상하 반전시 가장 안쪽 부터 바깥 방향으로 적용해나가야 한다는 것이죠. 그럼 왼쪽 아래 영역부터 상하 반전을 먼저 적용하도록 하죠.

상하 반전된 왼쪽 아래 영역을 문자열로 표현하면 다음과 같아집니다.

 

"x" + "w"(lb-lb) + "b"(lb-rb) + "b"(lb-lt) + "w"(lb-rt)

 

이제 가장 바깥쪽의 4가지 영역을 상하 반전을 시켜주면 됩니다.

상하 반전된 문자열로 표현하면 다음과 같아집니다.

"x" + "xwbbw"(lb-상하 반전됨) + "b"(rb) + "b"(lt) + "w"(rt)

쿼드트리 "xbwxwbbwb"는 상하 반전시키면 결과로 "xxwbbwbbw"가 되는 것이죠. 여기서 중요한 점은 어떻게 문자열을 4개의 영역으로 쪼갤 수 있을까입니다. 왜냐하면 2번째 입력처럼 4가지 영역안에 또 4가지 영역으로 쪼개지는 것은 거의 무한하게 쪼개질 수 있기 때문이죠. 하지만 다음의 규칙이 존재합니다.

 

1. 쿼드 트리 문자열에서 왼쪽 위 영역의 시작점은 x가 나타난 위치로부터 오른쪽으로 한 칸 이동한 곳이다.
2. 쿼드 트리 문자열에서 오른쪽 위 영역의 시작점은 왼쪽 위 영역이 끝나는 지점이다.
3. 쿼드 트리 문자열에서 왼쪽 아래 영역의 시작점은 오른쪽 위 영역이 끝나는 지점이다.
4. 쿼드 트리 문자열에서 오른쪽 아래 영역의 시작점은 왼쪽 아래 영역이 끝나는 지점이다.

무슨 말이냐면, 첫 번째 입력을 살펴보겠습니다.

 

"xbwwb" =>
    "x" (index = 0)
    "b" (lt: x가 나온 위치로부터 오른쪽 1칸 뒤, 쪼갠 위치: index + 1)
    "w" (rt: lt를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이)
    "w" (lb: rt를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이 + rt의 길이)
    "b" (rb: lb를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이 + rt의 길이 + lb의 길이)

 

두 번째 입력을 살펴볼까요?

 

"xbwxbwwbwb" =>
   "x" (index = 0)
   "b" (lt: x가 나온 위치로부터 오른쪽 1칸 뒤, 쪼갠 위치: index + 1)  
    "w" (rt: lt를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이)

    "xbwwb" (lb: rt를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이 + rt의 길이) =>
        "x" (index = lb가 시작된 위치, index + 1 + lt의 길이 + rt의 길이)
        "b" (lb-lt, index = lb가 시작된 위치 + 1)
        "w" (lb-rt, index = lb가 시작된 위치 + 1 + lb-lt의 길이)
        "w" (lb-lb, index = lb가 시작된 위치 + 1 + lb-lt의 길이 + lb-rt의 길이)
        "b" (lb-rb, index = lb가 시작된 위치 + 1 + lb-lt의 길이 + lb-rt의 길이 + lb-lb의 길이)

    "b" (rb: lb를 쪼갠 위치로부터 오른쪽 한 칸 뒤, 쪼갠 위치: index + 1 + lt의 길이 + rt의 길이 + lb의 길이)

 

결국 각 영역을 쪼개는 것은 다음처럼 나타낼 수 있습니다.

 

x: 영역의 시작점, index
lt: x위치의 바로 오른쪽, index + 1
rt: lt의 끝나는 지점 바로 오른쪽, index + 1 + lt의 길이
lb: rt의 끝나는 지점 바로 오른쪽, index + 1 + lt의 길이 + rt의 길이
rb: lb의 끝나는 지점 바로 오른쪽, index + 1 + lt의 길이 + rt의 길이 + lb의 길이

 

이해가 되셨나요? ㅎㅎ 이제 문제를 풀기 위한 조각들은 모두 모았습니다. 이를 코드로 표현하기만 하면 되지요. 위의 설명이 잘 이해가 안되신다면 아래 코드와 같이 번갈아서 살펴보세요. 그럼 이해하는데 도움이 될겁니다. 이를 코드로 표현하면 다음과 같아집니다.

 

string solution(const string & s, int index) {
    // 예외 상황 문자열을 모두 순회했을 경우입니다.
    if (index >= s.length()) {
        return "";
    }

    char at = s[index];
    // w라면 w를 반환합니다.
    if (at == 'w') {
        return "w";
    }
    
    // b라면 b를 반환합니다.
    if (at == 'b') {
        return "b";
    }
    
    // x라면 내부 쿼드 트리를 상하 반전 후 그 문자열을 반환합니다.
    // lt의 시작 위치는 index + 1
    index += 1;
    string lt = solution(s, index);
    // rt의 시작 위치는 lt 가 끝나는 지점, index + 1 + lt의 길이
    index += lt.length();
    string rt = solution(s, index);
    // lb의 시작 위치는 rt 가 끝나는 지점, index + 1 + lt의 길이 + rt의 길이
    index += rt.length();
    string lb = solution(s, index);
    // rb의 시작 위치는 lb 가 끝나는 지점, index + 1 + lt의 길이 + rt의 길이 + lb의 길이
    index += lb.length();
    string rb = solution(s, index);
    // 상하 반전은 x + lt + rt + lb + rb => x + lb + rb + lt + rt
    return "x" + lb + rb + lt + rt;
}

코드 전문

다음은 알고리즘 풀이 코드 전문입니다. 위에서 설명하지 않은 main 함수에서 문제의 입력을 다루고 있으니 유의해서 봐주세요!

 

#include <iostream>
#include <string>

using namespace std;

string solution(const string & s, int index) {
    if (index >= s.length()) {
        return "";
    }

    char at = s[index];

    if (at == 'w') {
        return "w";
    }

    if (at == 'b') {
        return "b";
    }
    
    index += 1;
    string lt = solution(s, index);

    index += lt.length();
    string rt = solution(s, index);

    index += rt.length();
    string lb = solution(s, index);

    index += lb.length();
    string rb = solution(s, index);
    
    return "x" + lb + rb + lt + rt;
}

int main() {
    int C;
    cin >> C;

    if ( !(0 < C && C <= 50) ) {
        cout << "fail: C is out of range, it must between 0 to 50" << endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        string s;
        cin >> s;

        if (s.length() > 1000) {
            cout << "fail: s is out of range it msut less equal than 1000" << endl;
            return 0;
        }

        string result = solution(s, 0);
        cout << result << endl;
    }

    return 0;
}

 

다음 코드를 제출하면, 5ms 이내로 통과하는 것을 확인할 수 있습니다.