[백준 1992 파이썬] 쿼드트리 (실버1, 분할 정복)

알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

N = int(input())
img = [list(map(int, input())) for _ in range(N)]

def quadrant(x, y, size):
    x1 = x + size
    y1 = y + size
    yield x, y
    yield x, y1
    yield x1, y
    yield x1, y1
    
def zipping(x, y, size):
    if size == 1:
        return str(img[x][y])
    
    check = img[x][y]
    isColor = True
    for i in range(x, x+size):
        for j in range(y, y+size):
            if check != img[i][j]:
                isColor = False
                break
                
    if isColor:
        return str(check)
    else:
        result = "("
        for u, v in quadrant(x, y, size // 2):
            result += zipping(u, v, size // 2)
        result += ")"
        return result

print(zipping(0, 0, N))

# 이 문제는 이 전의 2630 - 색종이 만들기와 달리, 모두가 1이거나 0인 박스인 경우를
# 따로 판별해서 걸러내주는 코드로 작성하지 않으면 답을 구할 수 없다.
# 색종이 문제의 경우 4x4 전부 1인 것에 대해, 개수 다 더해서 4되고 이 경우 white
# count가 0이 되므로, 조건문에서 이 경우를 걸러내어 (0, 1)을 반환해서 답이 잘 나오
# 게되지만, 이 문제의 경우는 바로바로 result에 4분할 반환값을 더해줘버리므로,
# for 이후에 조건문으로 후처리를 해줄 수가 없기 때문에 애초에 싹 다 0, 1인 박스인
# 경우를 걸러줘야한다.

풀이 요약

1. 분할 정복으로 풀기. 현재 size x size 크기의 박스가 1로만 이루어진 영상, 0으로만 이루어진 영상의 개수를 구하기 위해, size // 2 크기의 박스로 4분할해서, 각각의 only 1, 0인 img를 구한다.

2. 전체 문제, 즉 slicing의 반환은 괄호를 포함하여, 전체가 1 또는 0이면 1이나 0을 반환하고 (1) 이런 식으로.

   그게 아니면 4분할해서 각각의 반환값을 괄호 안에 집어넣어 반환해준다. 이 때, 4분할 각각의 반환값은 1이나 0일 수도 있고, 또 4분할이 되어서 괄호에 싸인 값일 수도 있다.

3. 전체가 1 또는 0인 경우를 미리 걸러내주지 않으면, 4분할 for 구문에서, 예를 들어 2x2 box가 다 1인 경우, 1을 4번 더해서 이 호출의 반환값은 (1)이 아니라 (1111)이 되버린다. check 변수 활용해서 미리 걸러주자

4. 4분할 for는 제너레이터 활용해서 짧고 간결한 구문으로 만듦.

배운 점, 어려웠던 점

• 왜 전체 1 or 0인 경우를 미리 걸러내주지 않으면 (1)이 아니라 (1111) 이렇게 리턴값이 나오는걸까 생각하는 데에, 컴퓨팅적 사고로 흐름을 따라가보느라 꽤나 애먹었다.

• 제너레이터와 분할정복에 조금 익숙해진 것 같다.