[백준 2630] 색종이 만들기 (python)

2630번: 색종이 만들기

---

 

queue를 만들어서 확인할 색종이들을 저장해서 해결

1. 전체에서 색이 다르다면, queue(꼭지점 네개)에 4등분 해서 넣어줌
2. 같다면 blue, white 카운팅

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))

white = 0
blue = 0
queue = deque([[0, 0, N, N]])

while queue:
    x1, y1, x2, y2 = queue.popleft()
    start = arr[x1][y1]
    half = (x2 - x1)//2

    flag = False
    for i in range(x1, x2):
        for j in range(y1, y2):
            if arr[i][j] != start:
                flag = True
                queue.append([x1, y1, x1+half, y1+half])
                queue.append([x1+half, y1, x2, y1+half])
                queue.append([x1, y1+half, x1+half, y2])
                queue.append([x1+half, y1+half, x2, y2])
                break
        if flag:
            break

    if not flag:
        if start:
            blue += 1
        else:
            white += 1

print(white)
print(blue)