[알고리즘][Python] 백준(BOJ) 2630 색종이 만들기_파이썬

 

2630 색종이 만들기    www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

문제 풀기 전 공부할 것 : 분할 정복, 재귀

 

 

 

 

 

 

 

 

 

 

풀이 1

<내용>

• 해당 범위의 색종이 색이 모두 같은지 확인하는 check 함수를 정의한다.
• solve 함수를 통해 check 함수를 부르고 해당 범위의 색종이 색이 모두 같으면 색종이 개수를 추가하고 같지 않으면 색종이를 나눈다.

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
white, blue = 0, 0

def check(i, j, d):
    std = paper[i][j]
    for x in range(i, i+d):
        for y in range(j, j+d):
            if paper[x][y] != std:
                return False
    return True

def solve(i, j, d):
    global white, blue
    
    if check(i, j, d):
        if paper[i][j]:
            blue += 1
        else:
            white += 1
        return
    else:
        d //= 2
        solve(i, j, d)
        solve(i, j+d, d)
        solve(i+d, j, d)
        solve(i+d, j+d, d)
        return
    
solve(0, 0, n)
print(white)
print(blue)

 

 

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• check 함수에서 False면 -1을 True면 색종이 색을 return 하도록 바꾼다.
• solve 함수에서 k가 1이라면 check 함수로 확인하지 않고 바로 색종이 개수를 추가한다.
• solve 함수에서 k가 1이 아니라면 check 함수 return이 -1인지 확인하고 -1이면 쪼개는 방법, 아니면 색종이 개수 추가하는 방법으로 바꾼다.

 

 

<코드>

import sys
input = sys.stdin.readline

def check(i, j, gap):
    color = paper[i][j]
    for x in range(i, i+gap):
        for y in range(j, j+gap):
            if color != paper[x][y]:
                return -1
    return color        

n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split(' '))))
    
cnt = [0, 0]
def solve(i, j, k):
    global cnt
    
    if k == 1:
        cnt[paper[i][j]] += 1
        return
    
    if check(i, j, k) == -1:
        k //= 2
        for p in range(2):
            for q in range(2):
                solve(i+k*p, j+k*q, k)
                
    else:
        cnt[check(i, j, k)] += 1
        
solve(0, 0, n)
for i in cnt:
    print(i)