[2630] 색종이 만들기

2630번: 색종이 만들기

종이의 색깔이 지정되어있고, 정사각형 모양으로 4등분해서 같은 색 종이로만 분해하는 것이 목적이고, 각 색깔별로 개수를 출력해야한다. 종이의 개수는 하얀색 W, 파란색 B에 담는다. 큰 종이가 있는 상태에서 4조각으로 나누어서 색이 다른 경우에는 다시 쪼개는 패턴이 있다. 그러면 생각해야되는 부분이 종이의 색이 다른가? 를 체크하는 방식인데..

정말 다행이도 N이 2, 4, 8, 16, 32, 64, 128 중 하나라고 나타나있어서 최대 128일때 이중 for문을 이용해서 각 종이의 색을 일일히 체크하는 방식으로 해도 시간초과가 걸리지 않을 것이다.

방법은 단순하다.

왼쪽 위 좌표와 오른쪽 아래 좌표를 받는 diff_color 라는 함수를 작성한다. 해당 함수에서는 좌표 사이에 색이 다른 것이 있는지 체크한다.

def diff_color(x1, y1, x2, y2):
    color = papers[x1][y1]
    is_same = True
    for i in range(x1, x2):
        for j in range(y1, y2):
            if color != papers[i][j]:
                is_same = False
                break

만약 해당 범위의 색이 같으면 True를 반환하는데, True 일때 해당 종의의 색 카운트를 +1 한다.

    if is_same:
        if color == 0:
            W += 1
        else:
            B += 1
        return

색이 다른 경우… 4조각으로 나누어야 하는데, 단순히 search 를 4조각의 범위에 맞게 호출하면 된다.

    else:
        diff_color(x1, y1, (x1 + x2) // 2, (y1 + y2) // 2)
        diff_color(x1, (y1 + y2) // 2, (x1 + x2) // 2, y2)
        diff_color((x1 + x2) // 2, y1, x2, (y1 + y2) // 2)
        diff_color((x1 + x2) // 2, (y1 + y2) // 2, x2, y2)

여기서 문제는 DP가 되는데 4조각으로 나눌수 없을때까지 나눌 수 있기 때문에 나눌 수 없을때 값을 반환해주어야 한다. 나눌 수 없다는 것은 한변의 길이가 1이면 나눌수 없기 때문에 해당 조건을 추가해준다.

    if abs(x2 - x1) == 1:
        if color == 0:
            W += 1
        else:
            B += 1
        return

이러면 DP로 한변의 길이가 1일때 해당 종이의 숫자를 +1 해서 return 하기 때문에 가장 작은 종의의 수까지 DP 스택이 된다. 여기까지 오면, 같은 색의 가장 작은 단위의 종이까지 탐색하게 되어서 모든 색 종이의 수를 각각 출력할 수 있다.

풀이

import sys

def diff_color(x1, y1, x2, y2):
    color = papers[x1][y1]
    global W
    global B
    if abs(x2 - x1) == 1:
        if color == 0:
            W += 1
        else:
            B += 1
        return

    is_same = True
    for i in range(x1, x2):
        for j in range(y1, y2):
            if color != papers[i][j]:
                is_same = False
                break

    if is_same:
        if color == 0:
            W += 1
        else:
            B += 1
        return
    else:
        diff_color(x1, y1, (x1 + x2) // 2, (y1 + y2) // 2)
        diff_color(x1, (y1 + y2) // 2, (x1 + x2) // 2, y2)
        diff_color((x1 + x2) // 2, y1, x2, (y1 + y2) // 2)
        diff_color((x1 + x2) // 2, (y1 + y2) // 2, x2, y2)

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    papers = list()
    W = 0
    B = 0
    for i in range(N):
        colors = list(map(int, sys.stdin.readline().split()))
        papers.append(colors)

    diff_color(0, 0, N, N)

    print(W)
    print(B)