[Baekjoon] 1992. 쿼드트리

🔗 Problem Link

1992번: 쿼드트리

---

❔Thinking

• 0과 1로 이루어진 2차원 데이터 구조를 압축한 결과를 반환한다.
• 해당 구조가 모두 0이거나 모두 1이 아닐경우, 사분면으로 나누어 다시 압축을 시도한다.

---

💻Solution

import sys
input = sys.stdin.readline

N = int(input())
board = []
result = ''
for _ in range(N):
    board.append(list(map(int, input().rstrip())))

def check(x,y,size):
    global board
    flag = board[x][y]
    for i in range(x,x+size):
        for j in range(y,y+size):
            if board[i][j] != flag:
                return False
    return True

def dfs(x,y,size):
    global board
    global result
    if size == 1 or check(x,y,size) is True: # board가 모두 0 혹은 1인 경우
        result += str(board[x][y])
        return
    result += '('
    size //= 2
    tmp = []
    # 1사분면
    dfs(x,y,size)
    # 2사분면
    dfs(x,y+size,size)
    # 3사분면
    dfs(x+size,y,size)
    # 4사분면
    dfs(x+size,y+size,size)
    result += ')'

dfs(0,0,N)
print(result)

---

🗝️keypoint

1. board와 반환할 result를 global변수로 정의하여 함수들이 호출되면서 board와 result를 활용할 수 있도록 한다.
2. 사분면으로 나누기 때문에, 매번 board의 사이즈를 반으로 줄여가며 확인한다.