164. 2630 (색종이 만들기) - 파이썬

import sys
input = sys.stdin.readline

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

result = []


def find(x, y, N):
    color = paper[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != paper[i][j]:
                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)
                return
    if color == 0:
        result.append(0)
    else:
        result.append(1)


find(0, 0, N)
print(result.count(0))
print(result.count(1))

문제요약

N*N 이 같은 색인 색종이를 만들어라

설명

분할정복에 대해서는 아래를 참고하자.

https://smhope.tistory.com/432?category=1056187 

[알고리즘 | 자료구조] 분할정복

먼저 그림을 통해서 문제를 이해해보자.

이미지 출처: https://st-lab.tistory.com/227

위와 같이 N*N이 같은 색상이 되도록 분할로 처리한다.

 

각 사분면을 나누기 위해서 아래 식을 사용할 것이다.

                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)

순서대로 1사분면, 2사분면, 3사분면, 4사분면으로 그림으로 나타내면 다음과 같다.

다시말해 현재 4사분면과 같이 완벽한 N*N사각형이 되지 않는이상 계속해서 나눌 것이다.

 

    color = paper[x][y]

먼저 각 사분면 첫부분을 color로 지정한다.

    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != paper[i][j]:
                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)

각 사분면에 들어있는 값을 비교하는데 만약  color와 다르면 나누기를 진행한다.

여기서 color와 다르다는 것은 완전한 색상의 N*N 사각형을 이루지 않는다와 같은 뜻이다.

 

    if color == 0:
        result.append(0)
    else:
        result.append(1)

나누는 작업을 진행하지 않았으면 온전한 N*N행렬로 만약 color가 0이면 result에 0을 넣고 color가 1이면 result에 1을 넣는다.

 

print(result.count(0))
print(result.count(1))

각 색상을 가지는 색종이가 몇개 인지 확인하여 출력해준다.