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

문제설명

• 아래 색종이 만들기 문제와 아주 유사한 문제였다.
• 부분적인 조건만 추가해서 DFS 방식으로 풀어주면 된다.

2021.03.15 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 색종이 만들기 2630 (파이썬)

[백준] 색종이 만들기 2630 (파이썬)

코드

# 쿼드트리
import sys

def quadTree(x,y,size):
# 전체 갯수를 센다. 
    color = matrix[x][y]

    if (size == 1):
        print(matrix[x][y], end='') #조각이 하나라면 더이상 나눠지지 않기 때문에 바로 프린트
        return
    flag = True
    for i in range(x,x+size):
        if not flag:
            break
        for j in range(y,y+size):
            if matrix[i][j] != color:
                flag = False
                break
    if flag:
        print(matrix[x][y], end='')
    else:
        print('(', end='')
        # 4등분 하기
        quadTree(x, y, size//2)
        quadTree(x,y+ size//2, size//2)
        quadTree(x+ size//2, y,size//2)
        quadTree(x+ size//2, y+size//2, size//2)
        print(')' ,end='')
    return

n = int(sys.stdin.readline().rstrip())
matrix = []
for _ in range(n):
    matrix.append(list(map(int,sys.stdin.readline().rstrip())))

quadTree(0,0,n)