[백준] 2630 - 색종이 만들기

floatFirstTOC: right

🖥️ 시작하며

1. color 에 현재 부분 종이의 첫 번째 칸의 색을 저장한다.

2. 이 부분 종이의 모든 칸을 검사한다.

for i in range(x, x + n):
    for j in range(y, y + n):
        if paper[i][j] != color:

• 만약 검사 도중 다른 색깔이 발견되면, 현재의 n x n 부분 종이는 더 이상 하나의 색깔로 이루어져 있지 않으므로 네 개의 작은 n/2 x n/2 부분 종이로 나누어 재귀적으로 처리한다.

if paper[i][j] != color:
    n_2 = n // 2
    return [
		    # zip과 sum(a)를 사용하여 각각의 재귀 호출로부터 반환된 결과(하얀색 종이와 파란색 종이의 개수)를 
		    # 합친다.
        sum(a)
        for a in zip(
            count_paper(x, y, n_2),
            count_paper(x, y + n_2, n_2),
            count_paper(x + n_2, y, n_2),
            count_paper(x + n_2, y + n_2, n_2),
        )
    ]

3. 네 개의 작은 부분 종이를 재귀적으로 처리한 결과를 합쳐서 반환한다.

4. 만약 부분 종이의 모든 칸이 같은 색깔로 이루어져 있으면, 해당 색깔의 종이 개수 리스트를 반환한다.
• [1, 0] : 하얀색 종이가 하나, 파란색 종이가 0개
• [0, 1] : 파란색 종이가 하나, 하얀색 종이가 0개

return [1, 0] if color == 0 else [0, 1]

⚙️ Python

def count_paper(x, y, n):  # 재귀적으로 색종이 분할
    color = paper[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if paper[i][j] != color:
                n_2 = n // 2
                return [
                    sum(a)
                    for a in zip(
                        count_paper(x, y, n_2),
                        count_paper(x, y + n_2, n_2),
                        count_paper(x + n_2, y, n_2),
                        count_paper(x + n_2, y + n_2, n_2),
                    )
                ]
    return [1, 0] if color == 0 else [0, 1]


if __name__ == "__main__":
    import sys

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

    white, blue = count_paper(0, 0, N)
    print(white)
    print(blue)

📌 소감