Algorithm/Algorithm Problem
백준 1780 종이의 개수
땅지원
2022. 3. 6. 16:55
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
종이에 써져있는 숫자가 모두 같다면 그걸 하나로 보고 아니면 9개로 자른다.
9개로 자른다는것은 사각형의 좌측상단. 즉 처음 시작점에 대한 좌표를 알아내면 된다.
각 좌표는 (x + i * n//3, y + j * n//3)라는 규칙을 가지고 있다.
처음에 0,0으로 시작해서 0,0이 -1, 0, 1인지 기준을 잡은다음에 n x n까지 돌리는데
만약 1개라도 잘못 나오게 된다면 그 즉시 그 종이는 잘못된것이므로
9개로 나눠서 분할정복을 시작하고 원래 있던건 return을 통해 없애준다.

def divide_paper(x,y,n):
std = paper[x][y]
for i in range(x,x+n):
for j in range(y,y+n):
if paper[i][j] != std:
for a in range(3):
for b in range(3):
divide_paper(x+a*n//3, y+b*n//3, n//3)
return
if std == -1:
data[0] += 1
elif std == 0:
data[1] += 1
else:
data[2] += 1
n = int(input())
paper = []
data = [0,0,0]
for _ in range(n):
paper.append(list(map(int,input().split())))
divide_paper(0,0,n)
for i in data:
print(i)