[백준] 2630. 색종이 만들기

문제

문제 링크

4분할로 나누면서 색종이들의 색깔에 맞춰 구역을 나누는 것이다. 큰 색종이부터 시작하여, 같은 색이 들어있을 때까지 2씩 나눈다.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

접근

1. 제일 먼저 0,0부터 시작하여 n 개수만큼 반복을 돌린다.
2. 처음 색깔을 추출하여, 처음 색깔과 다를 때 각각 1사분면, 2사분면, 3사분면, 4사분면을 탐색하고 다 탐색했을 경우 return
3. 처음색깔과 모두 똑같다면 그대로 나옴
4. 반복문을 빠져나오면 white값은 white, blue값은 blue로 저장하고 +1씩 해줌 -> return
   
   

코드

def Color(x,y,n):
    global white,blue     
    check=Mat[x][y]

    for i in range(x,x+n):
        for j in range(y,y+n):
            if check!=Mat[i][j]:     #나머지 사각형의 색깔과 일치하지 않는다면 실행합니다.
                Color(x,y,n//2)            #1사분면
                Color(x,y+n//2,n//2)       #2사분면
                Color(x+n//2,y,n//2)       #3사분면
                Color(x+n//2,y+n//2,n//2)  #4사분면
                return

    if check==0:
        white+=1
        return
    else:
        blue+=1
        return


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

white,blue=0,0

Color(0,0,N)
print(white)
print(blue)

=> ㅜ는 N이다.