[알고리즘][Python] 백준 2630 색종이 문제 풀이

문제 출처 : www.acmicpc.net/problem/2630

2630번: 색종이 만들기

---

문제 해석 : 색종이를 계속해서 쪼개어 같은 색만 남을 때까지 자르는 행위를 하고 한 가지 색상으로만 된 색종이의 갯수를 출력하는 문제이다.

 

문제 풀이 :  전형적인 분할정복 문제로 아래의 풀이는 실제 배열을 잘라서 파라미터로 넘기고 이를 저장하는 방식으로 문제를 풀었다. 4 분할을 진행하기 때문에 2중 for문을 2번씩 도는 형식으로 진행된다.

 

가능한 다른 풀이 : 파라미터만을 가지고 연산을 진행해서 문제를 풀이할 수 있다.

 

---

풀이 코드

def check(arr2):
    length = len(arr2)
    first = arr2[0][0]

    for i in range(length):
        for j in range(length):
            if arr2[i][j] != first:
                return False
    return True


def solution(arr):
    global count_0
    global count_1

    if check(arr):
        if arr[0][0] == 1:
            count_1 += 1
            return True
        else:
            count_0 += 1
            return True
    else:
        div = len(arr)//2
        temp = []
        for i in range(2):
            start = (i) * div
            end = (i+1) * div
            new_arr = arr[start:end]

            for j in range(2):
                start_2 = (j) * div
                end_2 = (j+1) * div

                for element in new_arr:
                    temp.append(element[start_2:end_2])
                solution(temp)
                temp = []

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
count_0 = 0
count_1 = 0

solution(arr)
print(count_0)
print(count_1)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.