[2630] 색종이 만들기

문제 이해

일정한 크기로 잘라서 하얀색(0) 파란색(1) 출력하기
이진탐색(X) 분할정복 문제
유사문제 : Z, 쿼드트리 
타고 들어가면서 분할 해야 하니까 재귀함수로 만들어야겠다

---

코드 계획

입력받기
n
정답 담을 변수 만들기
white
blue
2차원 리스트 만들기 
paper에 입력 받은 값 append해서 입력 받기

1. 분할하는 함수 만들기
slice (매개변수 : size, 현재 위치 row, col)
new_size = size // 2

2. 모두 같은색인지 확인
처음 위치의 색을 기준으로 설정
이중 for문으로 하나씩 확인 (n번 반복하면 안 됨!!! row, col번씩 반복해야함)
만약 기준색과 다른 컬러가 나온다면 종료해버림
잘 종료했다면 모두 같은 구역이라는 뜻으로  갯수에 1을 더해 전역 정답 변수에 저장 후 종료

3. 아니라면 재귀함수 4개 (왼위, 오위, 왼아래, 오아래)
slice(new_size, row, col)
slice(new_size, row, col+new_size)
slice(new_size, row+new_size, col)
slice(new_size, row+new_size, col+new_size)

분할함수 호출하기
slice(size, 0,0)

---

2
0 0
0 0

4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0

 

 

 

import sys

input = sys.stdin.readline

n = int(input())

color = [0,0]

paper = []

for i in range(n):

    temp = list(map(int, input().split()))

    paper.append(temp)

def slice(size, row, col):

    new_size = size // 2

    cur_color = paper[row][col]

    is_diff = False

    for i in range(row, row+size):

        for j in range(col, col+size):

            if paper[i][j] != cur_color:

                is_diff = True

                if is_diff:

                    break

        if is_diff:

            break

    if is_diff:

        slice(new_size, row, col)

        slice(new_size, row, col+new_size)

        slice(new_size, row+new_size, col)

        slice(new_size, row+new_size, col+new_size)

    else:

        color[cur_color] += 1

    return

   

slice(n, 0, 0)

print(color[0])

print(color[1])