7.2 문제 : 쿼드 트리 뒤집기(Python)

문제 출처 : algospot.com :: QUADTREE

algospot.com :: QUADTREE

---

참고 자료 : [알고리즘2] 07.02 쿼드 트리 뒤집기 (QUADTREE) in 알고리즘 문제해결전략 (종만북) - YouTube

---

1. 문제 해결을 위한 사고 과정

(1) 무식하게 풀기

• 주어진 쿼드 트리 압축을 풀어서 실제 이미지를 얻고 상하 반전한 뒤 다시 쿼드 트리를 압축
• 하지만, 문제에서 주어진 제한에 의해 곧이곧대로 구현할 수 없음

 

• 이런 경우 선택할 수 있는 접근 방법은 다음과 같이 2 가지가 존재한다.
• 1. 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
• 2. 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작해서 최적화해 나가기

 

(2) 쿼드 트리 압축을 풀고 분할 하기

• 문제에서 주어진 쿼드 트리를 압축하여 표현한 문자열 s를 배열에 저장하여 구현
• 이 때, 기저 사례는 s의 첫 글자가 w나 b인 경우이고, 배열 전체에 해당하는 색을 칠하고 종료
• s의 첫 글자가 x인 경우 나머지 부분을 4가지로 분할하여 재귀 호출
• 하지만, 첫 글자가 x인 경우 나머지 부분을 4가지로 분할하기가 까다로움(각 부분의 길이가 일정하지 않기 때문)

 

• 이를 해결하기 위해 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만들어 사용할 수 있다.
• 만일 첫 글자가 x라면 4가지로 나뉜 조각의 1사분면은 바로 다음 인덱스부터 시작
• 함수가 i를 반환하면 다음 조각은 i+1부터 시작하는 것을 알 수 있고 이를 통해 나머지 부분을 분할 가능

 

• 그러나 다른 방법으로 s를 쪼개는 것이 아니라 필요한 만큼만 가져다 쓰도록 하는 함수를 만드는 방법이 있다.
• 반복자(iterator)를 통해 한 글자를 검사할때마다 다음으로 한 칸씩 옮겨 다음 글자를 검사하는 방식
• 필요한 만큼 s를 검사하고 한 구역에 대한 검사가 끝나 함수가 반환되면 자연스럽게 반복자는 다음 구역의 시작 위치를 가리키게 된다.

 

(3) 압축을 다 풀지 않고 뒤집기

• 위 방법을 사용할 경우 (1)에서 설명한 대로 문제의 제한 사항에 위배되는 결과를 초래함(문제의 최대 크기인 2^20 * 2^20 크기의 그림을 압축 해제 하면 약 1Tb의 메모리를 차지한다고 한다.)
• 압축을 해제한 결과를 메모리에 다 저장하는 대신 이미지를 곧장 뒤집은 결과를 생성하는 코드를 사용하면 해결이 가능하다.
• 전체가 한 가지 색이 아닌 경우(x인 경우) 재귀 호출을 이용하여 나눠진 4부분을 상하로 뒤집은 결과를 얻고 병합해서 답을 얻는다.

 

• 병합 과정은 다음과 같다.
• 1. 원본 그림을 4등분 해서 각 부분을 상하로 뒤집은 압출 결과를 얻는다.
• 2. 위의 2 조각과 아래의 2 조각을 바꾸면 최종적으로 뒤집은 형태의 그림이 완성된다.

---

2. 해설 풀이 방법

(1) 코드

def reverse(quad, it):
    head = quad[it]
    it += 1

    # 기저 사례 : 구역이 완전한 흰색이나 검은색인 경우 뒤집어도 결과는 변하지 않는다.
    if head == 'w' or head == 'b':
        return head, it

    # 혼합 구역인 경우 4분면으로 나눠 뒤집는다.
    part_one, it = reverse(quad, it) # 1사분면에 대한 뒤집기를 실행하고 인덱스 반환
    part_two, it = reverse(quad, it) # 2사분면, 3사분면, 4사분면에 대해 동일하게 실행
    part_three, it = reverse(quad, it)
    part_four, it = reverse(quad, it)

    return 'x' + part_three + part_four + part_one + part_two, it # 뒤집힌 결과를 문자열로 만들어 인덱스와 함께 반환


for tc in range(int(input())):
    quad = input()

    print(reverse(quad, 0)[0])

(2) 해설

• 문자열인 quad와 반복자를 의미하는 it를 매개변수로 사용한다.
• 인덱스를 가리키는 반복자 it에 대해서 quad[it](= head)를 검사한다.
• 그리고 반복자가 다음 인덱스를 가리킬 수 있도록 it를 증가시킨다.
• head가 w나 b인 경우 뒤집어도 그대로 이므로 반복자와 함께 반환
• head가 x인 경우 4 구역으로 나누어 다시 재귀 호출을 통해 검사한다.(이때, 호출 시 마다 it은 계속 증가함 -> 함수의 반환이 이뤄질 경우 자연스럽게 it은 다음 구역을 가리킨다.)
• 어떤 나누어진 1, 2, 3, 4 구역(혹은 분면)을 3, 4, 1, 2 순으로 반환하면 해당 구역은 뒤집힌 상태가 되고 모든 압축 문자열에 대해서 반환이 이루어진 경우 최종적으로 그림 전체가 반환되는 결과가 된다.

---

3. 시간 복잡도 분석

• reverse() 함수는 한 번 호출될 때 마다 주어진 문자열의 한 글자를 사용한다.
• 따라서 함수가 호출되는 횟수는 문자열의 길이에 비례하므로 O(n)
• 각 문자열을 합치는데 또 O(n)의 시간이 든다 해도 문제의 제한 시간 안에 충분히 수행 가능하다.

---

4. 후기

  코드 자체는 어렵지 않지만 다른 문제들과 마찬가지로 문제 해결을 위한 방법을 이해하는 것이 어려웠다. 당장 문제를 봤을 때 생각한 방법은 위 설명에 나와있는 것 처럼 모든 문자열 전체에 대해서 압축을 풀고 구간을 나눠서 뒤집은 다음 합치려는 생각을 했었다. 하지만 역시 틀린 방법이었고 풀이 해설을 보며 어떻게 저런 사고를 할 수 있을까 감탄하게 되었다. 문제를 보면 볼 수록 점점 자신감이 떨어지는 느낌이다. 그리고 애초에 분할 정복 파트인데 어떻게 분할해야 할지 감을 못 잡은 부분도 조금 문제가 있는거 같다.

  그래도 요즘 브레이브걸스가 떡상중인데 브레이브걸스가 떡상할 수 있었던 큰 이유 중 하나가 평소에 준비를 잘 해놨고 기회가 찾아왔을 때 준비된 역량으로 기회를 낚아챌 수 있지 않았나 생각한다. 프로그래밍 알고리즘도 마찬가지로 지금은 내 실력도 부족하지만 준비를 잘 해놓으면 언젠가 기회가 왔을 때 잡을 수 있지 않을까 자기 위안을 해본다ㅠ

---

github : Algorithmic_Problem_Soving_Strategies/q1_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies