문제 2630

풀이

재귀 문제.
모두 같은 색으로 칠해진 하얀색과 파란색 색종이의 개수 구하기
N*N 종이를 N/2*N/2 종이 4개로 나눌 수 있음

1. 현재 크기(N*N)의 색종이의 색이 모두 같은지 확인
2. 하나라도 다르면 4개의 재귀 호출 후, 종료
   • 1사분면: func(x+0, y+0, n//2)
   • 2사분면: func(x+0, y+n//2, n//2)
   • 3사분면: func(x+n//2, y+0, n//2)
   • 4사분면: func(x+n//2, y+n//2, n//2)
3. 모두 같으면(1*1 색종이인 경우 자기자신과 비교) count[현재색]++

정답

import sys
input = sys.stdin.readline

def func(x, y, n):
    check = board[x][y] # 첫번째 색으로 검사
    for i in range(x, x + n): # 현재 한 변=N
        for j in range(y, y + n):
            if board[i][j] != check: # 다르면 재귀 호출 4번
                for a in range(2):
                    for b in range(2):
                        func(x + a*n//2, y + b*n//2, n//2)
                return
    count[check] += 1

N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
count = {0: 0, 1: 0} # white, blue
func(0, 0, N) 
print(*count.values(), sep='\n')

제출

유사 문제

문제 1780