[코딩테스트] 백준 색종이 만들기(2630) 파이썬(Python)

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

2630번: 색종이 만들기

N = int(input())
array = []
for _ in range(N):
    array.append(list(map(int, input().split())))
zeros = 0
ones = 0
def solve(n,array):
    global zeros
    global ones
    all_zeros = True
    all_ones = True
    if n == 1:
        if array[0][0] == 0:
            zeros += 1
        else:
            ones += 1
        return
    for i in range(0, n):
        for j in range(0, n):
            if array[i][j] != 0:
                all_zeros = False
            if array[i][j] != 1:
                all_ones = False
    if all_zeros:
        zeros += 1
        return
    if all_ones:
        ones += 1
        return
    n = n // 2
    solve(n, [[col for col in row[:n]] for row in array[:n]])
    solve(n, [[col for col in row[:n]] for row in array[n:]])
    solve(n, [[col for col in row[n:]] for row in array[:n]])
    solve(n, [[col for col in row[n:]] for row in array[n:]])

solve(N, array) 
print(zeros)
print(ones)

저는 분할정복과 재귀를 이용해서 문제를 해결하였습니다.

solve() 함수를 확인해보겠습니다.

먼저 global 키워드로 함수 밖에 있는 zeros, ones의 값을 증가시킬 수 있도록 했습니다.

all_zeros, all_ones 변수를 설정하였습니다.

두 변수는 2차원 배열을 탐색할 때 원소가 모두 0으로 이루어져있는지, 모두 1로 이루어져 있는지 확인하는 변수로 사용하였습니다.

 

먼저 주어진 입력으로 들어오는 n과 2차원배열을 모두 확인하면서 2차원배열의 원소가 모두 0인지 ,1인지 확인합니다.

만약 모두 0이라면 zeros를 1증가 해주고, 모두 1이라면 ones를 1 증가해주고 함수를 종료합니다.

 

2차원 배열안의 값이 모두 0 혹은 1이 아니라면 n을 2로 나누어주고 다시 n으로 저장합니다.

그리고 array를 4등분을 하여 solve 함수로 전달합니다.

 

4등분은 예제에서의 1,2,3,4에 해당합니다.

 

재귀의 종료조건으로는 n이 1일때 종료되며

2차원배열의 원소값을 확인하여 0이면 zeros를 1 증가시켜주고, 1이라면 ones를 증가시켜주고 함수를 종료합니다.