태야

<내 코드>

n = int(input())
video = [list(input()) for _ in range(n)]


def divide(x, y, n):
    ans = []
    check = True
    color = video[x][y]

    for i in range(x, x+n):
        if not check:
            break
        for j in range(y, y+n):
            if color != video[i][j]:
                check = False
                ans.append("(")
                ans.extend(divide(x, y, n//2))
                ans.extend(divide(x, y+n//2, n//2))
                ans.extend(divide(x+n//2, y, n//2))
                ans.extend(divide(x+n//2, y+n//2, n//2))
                ans.append(")")
                return ans
    return color


print("".join(divide(0, 0, n)))

list.append와 list.extend의 차이에 대해 알게 됐다.

a = [1, 2, 3]
b = [4, 5, 6]

a.append(b)
print(a) # [1, 2, 3, [4, 5, 6]]

a = [1, 2, 3]
b = [4, 5, 6]

a.extend(b)
print(a) # [1, 2, 3, 4, 5, 6]

append는 해당 리스트(b) 그 자체를 리스트(a) 끝에 넣어준다. 반면에 extend는 해당 리스트(b) 안의 요소들을 (a)리스트 끝에 넣어 확장시켜준다.

<내 코드>

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]

white, blue = 0, 0


def divide(x, y, n):
    global white, blue
    color = paper[x][y]
    check = True

    for i in range(x, x+n):
        if not check:
            break

        for j in range(y, y+n):
            if color != paper[i][j]:
                check = False
                divide(x, y, n//2)  # 1사분면
                divide(x, y+n//2, n//2)  # 2사분면
                divide(x+n//2, y, n//2)  # 3사분면
                divide(x+n//2, y+n//2, n//2)  # 4사분면
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1


divide(0, 0, N)
print(white)
print(blue)

이 문제는 처음 접하는 개념인 '쿼드트리'를 만드는 것이었다. 트리의 자식노드가 4개씩 분할하는 방법이라고 한다.

여기서 분할 된 영역 안에서 같은 색인지 판단해 다르다면 또 다시 나누면서 찾아간다. 일반 동적 계획법과 다르게 분할 정복은 중복되는 하위 문제가 없다는 것이 차이다.