[BOJ 1992] 쿼드트리(Python)

---

문제

쿼드트리

---

문제 해설

주어진 2차원 리스트를 4분할하고 재귀탐색으로 답을 찾는 문제입니다.

주어진 리스트를 검사해서 전부 0 혹은 1일때는 괄호 없이 반환합니다.
그게 아니라면 괄호와 함께 11시, 1시, 7시, 5시 방향 순으로 재귀 탐색을 다시 진행하면 끝입니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
graph = [list(map(str, input().rstrip())) for _ in range(n)]
# 시작점의 좌표와 조사할 크기를 매개변수로
def dfs(x, y, size):
    if size == 1:
        return graph[x][y]
    # 전부 0 혹은 1인지 검사
    count = 0
    for i in range(x, x + size):
        for j in range(y, y + size):
            count += int(graph[i][j])
    if count == 0 or count == size ** 2:
        return "0" if count == 0 else "1"
    halfsize = size // 2
    return (
        "("
        + dfs(x, y, halfsize)
        + dfs(x, y + halfsize, halfsize)
        + dfs(x + halfsize, y, halfsize)
        + dfs(x + halfsize, y + halfsize, halfsize)
        + ")"
    )


print(dfs(0, 0, n))

---