[백준 2630] 색종이 만들기(python)

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

2630번: 색종이 만들기

색종이 만들기 문제

색종이의 가로 세로를 N//2 영역으로 만들어 내려갔을 때, 파란색 색종이 영역의 갯수와 흰색 색종이 영역(잘려나간 흰색 종이)의 갯수를 구하는 문제

분할 정복을 활용한 재귀를 이용하면 쉽게 풀 수 있다

⚙️내가 푼 정답코드

def div(y, x, n): 
    color = paper[y][x] # 색종이의 색
    for i in range(y, y+n): # y 분할 
        for j in range(x, x+n): # x 분할
            if color != paper[i][j]: # 찾는 과정에서 색이 달라지면
                m = n//2
                div(y, x, m) # 색종이 분할 (2사분면)
                div(y, x + m, m) # 색종이 분할 (1사분면)
                div(y + m, x, m) # 색종이 분할 (3사분면)
                div(y + m, x + m, m) # 색종이 분할(4사분면)
                return
    if color == 0: # 흰색이면
        result[0] += 1 #자르기
    else : # 파란색이면
        result[1] += 1 # 갯수세기
        
import sys
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 색종이
result = [0,0] # 자른 색종이 / 파란색 색종이
div(0,0,N)
print(result[0],'\n',result[1],sep='')

반응형

📌문제 접근 포인트

1. N//2로 반복해서 탐색해야한다. 반복해서 탐색하기에 재귀를 사용하면 된다는 것을 알 수 있다.
2. 반복 탐색 과정 중 N//2로 4면을 분할하는 과정을 거치므로 분할정복 알고리즘을 사용해야한다.
3. 먼저 탐색하려는 시작 색상을 정해주고, 주어진 영역에서 탐색하는 과정에서 색상과 일치하지 않는 지점이 생긴다면, 분할해서 탐색하도록 알고리즘을 구성해주자.
4. 탐색에 성공했다면, 그때 시작 색상에 따른 각각의 갯수를 세어주자