[알고리즘/파이썬] 백준 1992번 - 쿼드트리

 

 

 

백준에서 분할정복(divide and conquer)과 관련된 기초적인 문제를 풀어봤다. 분할정복은 이름에서도 알고리즘 컨셉을 유추할 수 있다. 한개의 큰 문제를 다수의 작은 문제로 쪼개고 쪼개진 문제의 해답을 구해 그 값들을 모으면 큰 문제의 해답이 된다는 개념.

 

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

1992번: 쿼드트리

 

 위 문제를 풀기위해서 재귀를 많이 사용한다. 재귀는 아래 그림과 같이 함수내에서 똑같은 함수를 다시 호출하는 방법을 말한다. 종료조건을 꼭 써줘야하며 그렇지 않으면 무한루프에 빠지게 된다. 

 

Test(3)을 실행 해보자. Test(n)을 계속해서 호출한다. n이 0과 같거나 그보다 작아지면 호출하지 않도록 코드가 작성되어있다.

 

쿼드트리 문제는 심플하게 아래 3개의 문장으로 정리된다.

1.이미지를 십자가 모양으로 쪼갠다.

2. 좌측상단,우측상단,좌측하단,우측하단을 확인을한다. 

3. 쪼개진 값이 모두 0 또는 1 이라면 출력한다. 그렇지 않다면 다시 1을 수행한다. 

 

4x4짜리 이미지 문제해결. 가장큰 문제 하나를 sub-Problem으로 쪼개고 조건을 만족하지 않으면 다시 해당 이미지를 쪼갠다.

 

 

위 그림을 소스코드로 구현. 2차원 list를 좌측상단부터 우측하단까지 잘 쪼개는게 관건. python은 numpy를 쓰면 2차원 list도 쉽게 slice할수 있다고 하는데 최대한 라이브러리를 쓰지않고 풀기위해 아래처럼 구현했다. 

# 정답을 담을 변수
result = []
def Test(a):

    # 모두 0이거나 모두 1이면 끝.
    if sum( sum(a,[]) ) == 0 or len( sum(a,[]) ) == sum(a,[]).count(1):
        if sum( sum(a,[])) == 0:
            result.append('0')
        else:
            result.append('1')
        return

    else:
        result.append('(')
        div = int(len(a)/2) # a/2 x a/2 크기의 행렬을 만들기위해.

        tmp_l =[] # 좌측
        tmp_r =[] # 우측

        # 한행씩 불러온다.
        for sub in a:
            # 1/2 앞쪽 열
            tmp_l.append(sub[0:div])
            # 1/2 뒷쪽 열
            tmp_r.append(sub[div:])

            # tmp_l,tmp_r이 div x div 크기라면
            if len(tmp_l) == div:
                Test(tmp_l) # 좌측값
                Test(tmp_r) # 우측값
                tmp_r = []
                tmp_l = []
        result.append(')')

n = input()
a = []
for i in range(int(n)):
    row = input()
    tmp = []
    for v in row:
        tmp.append(int(v))
    a.append(tmp)
Test(a)

print( ''.join(result) )