[백준] 2630 색종이 만들기 (Python 파이썬)

문제 설명

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

2630번: 색종이 만들기

 

---

풀이 과정

먼저, N x N 배열이 모두 같은 색으로만 이루어져 있지 않으면 ( 즉, 1로만 이루어져있거나 0으로만 이루어져있지 않으면)

4등분을 해야한다.

 

예를 들어, 8 x 8 배열에서 처음 종이를 자르게 된다면 8 / 2 x 8 / 2 ( = 4 x 4 ) 모양의 색종이로 4등분을 하게 된다.

그리고 이렇게 4등분된 색종이 중 하나가 또 모두 같은 색으로 이루어져 있지 않다면,

 

그 색종이를 이전과 같은 방식으로 N / 2 x N / 2 모양의 색종이로 4등분을 하게 된다.

 

이렇게 계속 같은 방식으로 나누기 때문에, 재귀적으로 접근을 해야 하며

또, 하나의 구역을 작은 구역들로 나누고, 또 그 작은 구역들을 더 작은 구역들로 나눠 문제를 해결해야 하므로

 

분할 정복 문제라고 볼 수 있다.

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

n = int(input())


def recursive(x, y, N):
    flag = False

    for i in range(x, x + N):
        if flag:
            break

        for j in range(y, y + N):
            if graph[x][y] != graph[i][j]:
                recursive(x, y, N // 2)
                recursive(x, y + N // 2, N // 2)
                recursive(x + N // 2, y, N // 2)
                recursive(x + N // 2, y + N // 2, N // 2)

                flag = True
                break

    if not flag:
        if graph[x][y] == 0:
            count[0] += 1
        else:
            count[1] += 1


graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

count = [0, 0]

recursive(0, 0, n)
for i in count:
    print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !