2022.02.21 [백준] (python 파이썬) 색종이 만들기

 

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

2630번: 색종이 만들기

---

풀이

재귀함수를 이용하여 분할정복으로 문제를 해결하였다.

 

우선 n이 1이면 더이상 분할이 되지않기 때문에 해당 인덱스값을 증가시켜주었다.(해당 색의 카운트를 증가)

그리고 check를 이용하여 해당 종이의 색을 for문을 돌려 확인하고 만약 다른 색이 있다면 check값을 False로 바꾸고 break를 이용하여 for문을 빠져나옴.

만약 check값이 True면 해당 종이의 색이 모두 같으므로 해당 색의 값을 증가시킴.

종이의 색이 다르다면 문제에서 주어진 대로 4등분하여 다시 분할된 종이를 확인함.

n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
ans=[0]*2
 
def Cal(n,x,y):
    if n==1:
        ans[arr[x][y]]+=1
        return
 
    check=True
    for i in range(x,x+n):
        for j in range(y,y+n):
            if arr[x][y]!=arr[i][j]:
                check=False
        if not check:
            break
 
    if check:
        ans[arr[x][y]]+=1
    else:
        a=n//2
        for i in range(2):
            for j in range(2):
                Cal(a,x+a*i,y+a*j)
Cal(n,0,0)
for i in ans:
    print(i)