[jungol] Intermediate_Coder / 분할과정복 / 1335 / T색종이 만들기(영역구분) / python

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=614&sca=3010 

JUNGOL

 

👀문제접근

1. 재귀함수를 이용해서 분할과 정복하자

2. 사각형의 왼쪽 위 좌표와 사각형 변의 길이를 파라미터로 갱신

3. 만약 사각형 내에 다른 색깔이 공존하면 왼쪽 위 좌표와 변의 길이를 4등분으로 조절하여 재귀함수 호출

4. 사각형 내에 색깔이 하나밖에 없다면 그 전역변수로 선언된 색깔 카운팅 + 1

 

🌈코드구현

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

blue = 0
white = 0

def check(x, y, size):
    global board
    global blue
    global white
    flag = True
    now = board[x][y]
    for i in range(x, x+size):
        for j in range(y, y+size):
            if board[i][j] != now:
                flag = False
                break
        if flag == False:
            break

    if flag == True:
        if board[x][y] == 1:
            blue += 1
        else:
            white += 1
        return

    else:
        check(x,y,size//2)
        check(x+(size//2), y, size//2)
        check(x, y+(size//2), size//2)
        check(x+(size//2), y+(size//2), size//2)

check(0, 0, N)

print(white)
print(blue)