[백준] 2630. 색종이 만들기 / python 파이썬

🚩 분할정복

 

thinking

N이 1이 될때까지 쪼개면서 체킹하자

그럼 어케 쪼갤 것이냐? → 시작점의 좌표를 구해서 종이크기만큼 range를 설정한 후, 범위 체킹하자.

반복문 돌리면서 체킹하다 색깔이 전부 같으면 거기는 stop하고 white or blue 개수에 카운팅해서 경우의 수를 줄이자

 

코드

def divide(s_x,s_y,N):
    global cnt_w, cnt_b
    if N == 1 and a[s_x][s_y] == 0:
        cnt_w += 1
        return
    if N == 1 and a[s_x][s_y] == 1:
        cnt_b += 1
        return

    flag_w = 0
    flag_b = 0
    for i in range(s_x, s_x+N):
        for j in range(s_y, s_y+N):
            if flag_w == 0 and a[i][j] == 0:
                flag_w = 1
            elif flag_b == 0 and a[i][j] == 1:
                flag_b = 1
    N //= 2
    if flag_w == 1 and flag_b == 0:  # 전부 하얀색인 경우 -> 하얀색 카운트하고 끝
        cnt_w += 1
    if flag_w == 0 and flag_b == 1:  # 전부 파랑색인 경우 -> 파랑색 카운트하고 끝
        cnt_b += 1
    if flag_w == 1 and flag_b == 1:  # 둘다 나오면 쪼개기
        divide(s_x, s_y, N)
        divide(s_x + N, s_y, N)
        divide(s_x, s_y + N, N)
        divide(s_x + N, s_y + N, N)



N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
cnt_w, cnt_b = 0, 0
divide(0, 0, N)
print(cnt_w, cnt_b)

 

 

한줄후기

할만했던 문제