[백준 2630번] 파이썬 - 색종이 만들기

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

 

# 조건

• 여러 개의 정사각형 칸들은 하얀색이나 파란색으로 칠해져있다.
• 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들자.
• 전체 종이 크기 NxN(N = 2^k)
• 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 크기가 똑같은 N/2 x N/2 크기의 색종이로 나눈다.
• 파란색이 1, 흰색이 0

 

# 접근 방법

• 분할 정복과 재귀를 이용하여 풀어주면 된다.
• 처음 시작하는 숫자를 기록해주고 2^k x 2^k 크기의 색종이가 똑같은 색깔이라면 출력, 그렇지 않다면 /2를 해준다.
• 최소 크기( = 1)이 된다면 +1
• 같은 색깔 확인하는 반복문이 정상종료 된다면 +1
• 또한 flag 변수를 선언해주어 현재 크기의 종이가 같은 색깔이 아닌 경우 반복문 종료를 시켜준다.

 

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
# 체크 함수 - x,y 시작위치, 현재 종이 크기  
def check(x,y,n):  
    global count, paper  
    # 종이의 크기가 최소라면 +1 후 종료  
    if n == 1:  
        count[paper[x][y]] += 1  
        return  
    # 반복문 탈출 위한 변수  
    flag = False  
    # 전체 크기 순회하기 전 시작 숫자 기록  
    start = paper[x][y]  
    # 시작위치부터 현재 잘려진 종이의 크기 순회  
    for i in range(x, x+n):  
        for j in range(y, y+n):  
            # 같지 않다면 재귀적으로 잘라준다.  
            if paper[i][j] != start:  
                # 시작부터 -> 시작 + 크기까지 -> 크기//2 만큼 등분시켜서 반복  
                for k in range(x, x+n, n//2):  
                    for j in range(y, y+n, n//2):  
                        check(k, j, n//2)  
                # 같지 않다면 자르기 전 크기의 종이 탐색 불필요  
                # 따라서 flag 변수를 통해 탈출                
                flag = True  
                break        
        if flag:  
            break  
    else:  
        # 다 같은 색의 종이라면 +1  
        count[start] += 1  
        return  
  
  
  
  
N = int(input())  
paper = [[*map(int, input().split())] for _ in range(N)]  
# 흰색 파란색 개수 체크  
count = [0,0]  
check(0,0,N)  
  
print(*count, sep='\n')