[BOJ 1780] 종이의 개수 파이썬

재귀를 사용하여 해결할 수 있는 분할 정복 문제입니다.

종이에 쓰여 있는 값이 모두 -1 또는 0 또는 1로 같지 않으면 모두 같아질 때까지 나누는 것을 반복합니다.

이 때, 함수의 parameter로 보고자 하는 부분의 종이(2차원 배열)을 넣어주고 싶었는데, 2차원 배열을 어떻게 잘라야 할 지 고민했습니다.

 

2차원 배열은 다음과 같이 자를 수 있습니다.

board =[
    [1, 1, 2, 2], 
    [1, 1, 2, 2],
    [3, 3, 4, 4],
    [3, 3, 4, 4]
]

size = 2
print([row[:size] for row in board[:2]]) #1부분

결국, 2차원 배열을 가로로 먼저 잘라주되 그 안에 있는 row들도 모두 쪼개주면 됩니다.

그리고 이것을 배열에 감싸서 2차원 배열로 만들어줍니다.

 

문제의 전체 코드는 다음과 같습니다.

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
ans1, ans2, ans3 = 0, 0, 0
# info = {
#     -1 : ans1,
#     0 : ans2,
#     1 : ans3
# }

def count(paper):
    global ans1, ans2, ans3
    size = len(paper)
    if size == 1:
        #info[paper[0][0]] += 1
        if paper[0][0] == -1: ans1 += 1
        elif paper[0][0] == 0 : ans2 += 1
        elif paper[0][0] == 1 : ans3 += 1
        return True
    elif size > 1:
        cnt1, cnt2, cnt3 = 0, 0, 0
        for i in range(size):
            for j in range(size):
                if paper[i][j] == -1:
                    cnt1 += 1
                elif paper[i][j] == 0:
                    cnt2 += 1
                elif paper[i][j] == 1:
                    cnt3 += 1

        if cnt1 == size*size:
            ans1 += 1
            return True
        elif cnt2 == size*size:
            ans2 += 1
            return True
        elif cnt3 == size*size:
            ans3 += 1
            return True
        

        #더 쪼개야함
        newSize = size // 3
        count([row[:newSize] for row in paper[:newSize]])
        count([row[newSize:newSize*2] for row in paper[:newSize]])
        count([row[newSize*2:] for row in paper[:newSize]])

        count([row[:newSize] for row in paper[newSize:newSize*2]])
        count([row[newSize:newSize*2] for row in paper[newSize:newSize*2]])
        count([row[newSize*2:] for row in paper[newSize:newSize*2]])

        count([row[:newSize] for row in paper[newSize*2:]])
        count([row[newSize:newSize*2] for row in paper[newSize*2:]])
        count([row[newSize*2:] for row in paper[newSize*2:]])

count(board)
print(ans1)
print(ans2)
print(ans3)

 

그리고 반복되는 코드를 줄이기 위해서 info라는 딕셔너리를 사용하려고 했지만, info의 value로 변수를 넣었더니 원하는 답이 나오지 않았습니다. 이러한 코드를 if문을 줄여서 깔끔하게 만들 수 있는 방법을 찾고 싶습니다..