[Baekjoon]백준 1992 쿼드트리(실버 1) - Python

문제설명 1

문제설명 2

문제를 살펴보면 이전 문제(2630 색종이 만들기)와 조건은 비슷하다

다른 점이라하면 비디오가 나누어질때마다 괄호가 출력되어야하며 각 색깔을 출력해야한다는 점이다

일단 입력받은 값을 처리하는 코드를 작성해주어야한다

이전까지 자주 사용하였던 input().split()이 아니라 공백없이 입력받으므로 input().strip()으로 입력받아야한다

size = int(input())
video = []
for _ in range(size):
    video.append(list(map(int, input().strip())))

그리고 이번에는 괄호가 포함되어있기 때문에 결과값을 저장하는 리스트를 따로 만들어주었다

이후 함수를 호출하고, 이를 언패킹하는 방식으로 출력하도록 하였다

result = []
sol(0, 0, size)
print(*result, sep = '')

이제 핵심은 sol함수인데, 일단 하나의 비디오의 첫번째 위치를 입력받으면 이를 기준으로 정하면 된다

이후에 두 개의 for문을 이용하여 해당 비디오의 색깔을 확인한다 만약 색깔이 다른 위치가 등장하게 되면

이전 문제처럼 x, y, size를 조절하여 재귀적으로 함수를 호출한다

여기서 중요한 점은 색깔이 다른 경우는 나뉘면서 괄호가 추가적으로 붙기 때문에 result배열에 '('와 ')'를

추가적으로 append해주어야한다 그리고 마지막에 해당 색깔을 append하는 코드를 넣어주면 된다

def sol(x, y, size):
    color = video[x][y] # 기준
    for i in range(x, x + size):
        for j in range(y, y + size):
            if color != video[i][j]:
                result.append('(')
                sol(x, y, size // 2)                            # 왼쪽 위
                sol(x, y + size // 2, size // 2)                # 오른쪽 위
                sol(x + size // 2, y, size // 2)                # 왼쪽 아래
                sol(x + size // 2, y + size // 2, size // 2)    # 오른쪽 아래
                result.append(')')
                return
    result.append(color)