백준 1780 [종이의 개수] 파이썬

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

1780번: 종이의 개수

#백준 1780 종이의 개수
import sys
input=sys.stdin.readline
minusone=0
zero=0
one=0
def all_same(p):
    global minusone #-1로 이루어진 종이의 개수를 담을 전역변수 생성
    global zero #0으로 이루어진 종이의 개수를 담을 전역변수 생성
    global one #1로 이루어진 종이의 개수를 담을 전역변수 생성
    len_p=len(p)    
    zero_cnt=0 #p에서 0의 개수를 담을 로컬변수 생성
    one_cnt=0 #p에서 1의개수를 담을 로컬변수 생성
    minusone_cnt=0 #p에서 -1의 개수를 담을 로컬변수 생성
    for i in range(len_p): #반복문을 돌며 각 개수 카운트
        for j in range(len_p):
            if p[i][j]==0:
                zero_cnt+=1
            elif p[i][j]==1:
                one_cnt+=1
            elif p[i][j]==(-1):
                minusone_cnt+=1
    if zero_cnt==(len_p*len_p): #모두 0으로 이루어져 있으면
        zero+=1
    elif one_cnt==(len_p*len_p): #모두 1로 이루어져 있으면
        one+=1
    elif minusone_cnt==(len_p*len_p): #모두 -1로 이루어져 있으면
        minusone+=1
    else: #그렇지 않으면
        rows=[val for val in range(0,len_p+1,len_p//3)] #행을 3분할
        columns=[val for val in range(0,len_p+1,len_p//3)] #열도 3분할
        for i in range(1,len(rows)):
            cut_rows=p[rows[i-1]:rows[i]] #행 자름
            for j in range(1,len(columns)):
                p_=list(zip(*cut_rows))[columns[j-1]:columns[j]] #열도 자름
                all_same(p_) #재귀로 반복


N=int(input())
paper=[]
for _ in range(N):
    paper.append(list(map(int,input().split())))
ans=all_same(paper)
print(minusone)
print(zero)
print(one)

2630번 색종이 만들기와 아주 유사한 문제였다. (어렵다..ㅠㅠ). 분할정복 연습을 좀 더 해야지. 

 

2630번 풀이와 마찬가지로 더 깔끔하게 푸신 분의 풀이가 있어 첨부한다.

import sys


def dfs(x, y, z):
    global answer
    visited = graph[x][y]

    # 반복문을 통해 종이를 확인
    for i in range(x, x + z):
        for j in range(y, y + z):
            # 시작점에 종이의 수가 현재 종이의 수와 다르다면
            if graph[i][j] != visited:
                # 3 * 3 범위를 재귀적으로 탐색
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * z // 3, y + l * z // 3, z // 3)
                return

    # 카운트
    if visited == -1:
        answer[0] += 1
    elif visited == 0:
        answer[1] += 1
    else:
        answer[2] += 1


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
answer = [0, 0, 0]
dfs(0, 0, n)
[print(res) for res in answer]

https://fre2-dom.tistory.com/412 <-- 링크