[BOJ] 색종이 만들기

---

코드

import sys
input = sys.stdin.readline

N = int(input())

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

white = blue = 0

def solution(x, y, N):
    color = graph[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != graph[i][j]:
                solution(x, y, N//2)
                solution(x, y + N//2, N//2)
                solution(x + N//2, y, N//2)
                solution(x + N//2, y + N//2, N//2)
                return

    global white, blue
    if color == 0:
        white += 1
    else:
        blue += 1
        
solution(0,0,N)

print(white)
print(blue)

결과

풀이 방법

• 좌표를 4개 정사각형으로 분할해 가면서 색종이가 될 수 있는 구역과 그 색깔을 찾는 분할정복, 재귀 문제이다
• solution 함수에서는 탐색시작 좌표의 색깔을 저장해 두고 해당 좌표로부터 매개변수로 주어진 N x N 만큼의 구역이 모두 같은 색깔인지 확인한다.
• 모두 같은 색깔이면 해당 구역은 색종이가 되고 색깔을 카운트한다
• 하나라도 다른 색깔이 발견되면 해당 구역은 색종이가 될 수 없으므로 4개 구역으로 다시 분할하여 각 구역에 대해 solution 함수를 실행한다.

---