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

---

문제 접근

n x n 행렬을 받아, 안의 모든 요소가 같다면 그대로 리턴, 같지 않다면 행과 열을 절반으로 나누어 4개의 행렬로 분할하여 각각 재귀호출한다.

재귀함수를 하나 만들었고, 하얀 색종이와 파란 색종이 영역이 각 몇 개씩인지 세야 하므로 count[]라는 배열을 만들어 영역이 1로 채워진 경우 count[1]에, 영역이 0으로 채워진 경우 count[0]에 더해지도록 했다.

 

가장 중요한 부분은 행렬을 4개로 분할하는 것인데, 파이썬의 slicing을 사용했다.

현재 행(열) 사이즈를 절반으로 나누어 new_size에 할당하고 이를 이용해 2*2 for loop를 돌며 새로 만들(분할된) 행렬의 범위를 슬라이싱으로 정해주었다.

 

정답 코드

#2630: 색종이 만들기

import sys

def count_picture(matrix, count):
    size = len(matrix)
    flag = 0
    first = matrix[0][0]
    for i in range(size):
        for j in range(size):
            if matrix[i][j] != first:
                flag = 1
                break
    if flag == 1:
        new_size = size // 2
        for i in range(2):
            row_start = i*new_size
            row_end = row_start + new_size
            for j in range(2):
                column_start = j*new_size
                column_end = column_start + new_size
                new_matrix = [row[column_start:column_end] for row in matrix[row_start:row_end]]
                count_picture(new_matrix, count)
    else:
        count[matrix[0][0]] += 1
        return

n = int(sys.stdin.readline().rstrip())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
count = [0, 0]

count_picture(matrix, count)
print(count[0])
print(count[1])

---

2630번: 색종이 만들기