2630. 색종이 만들기

 

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

✔ 유형 : 이분 탐색

✔ 문제 풀이: 큰 문제를 작은 문제로 분할하여 작은 문제부터 순차적으로 해결한 뒤 결과를 합한다.

 

 

탐색할 영역의 제일 왼쪽 위의 색을 저장해두고, 이중 for문으로 다른 색이 포함되어 있는지 확인한다.

만약 다른 색이 포함되어있다면 각 면을 N/2로 나눠서 총 4 부분으로 나눈다.

계속 나누다가 언젠간 한면이 1이되면 해당 색을 배열에 저장한다. 만약 한 구역을 검사했는데 모두 같은 색이라면 해당 색을 배열에 저장한 후 함수를 리턴한다.

 

위의 방법을 아래의 코드로 나타내었다.

 

import sys
input=sys.stdin.readline # input함수 바꾸기
import copy
#input
N = int(input()) # 종이의 크기

W=[[*map(int,input().split())] for _ in range(N)] # 정리 해두기 N행 배열 입력 받는 법

result = []

#크기가 4씩 나눠짐.
def divided_conquer(div, start): # start = {x,y}
    color = W[start[0]][start[1]]

    for i in range(start[0], start[0] + div):
        for j in range(start[1], start[1]+div):
            if color != W[i][j]:
                # 만약 다른 색이 나온다면 분할한다.
                divided_conquer(div//2, start) 
            
                divided_conquer(div//2, [start[0], start[1]+ div//2 ])
            
                divided_conquer(div//2, [start[0]+ div//2 , start[1]])
            
                divided_conquer(div//2, [start[0]+ div//2 , start[1]+ div//2 ])
                
                return
            
                
    if color == 0:
        result.append(0)
    else:
        result.append(1)
        
    
    return 



divided_conquer(N, [0,0])

print(result.count(0))
print(result.count(1))