알고리즘/백준(BOJ)
[백준/BOJ]#1780: 종이의 개수 [분할정복/재귀/파이썬/python]
숲호랑이
2022. 1. 13. 17:04
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
분할정복과 재귀를 이용하여 푸는 문제다.
dfs bfs가 생각났는데 분류가 분할정복으로 되어있고 9개로 종이개수가 정해져있으므로
for문으로 돌리고 재귀를 해서 체크하면 된다.
#1780_종이의개수_dividenconquer
n=int(input())
paper = [list(map(int,input().split())) for _ in range(n)]
res1=0
res0=0
res_1=0
def search(x,y,k):
global res1, res0, res_1
checkboard=paper[x][y]
for i in range(x,x+k):
for j in range(y,y+k):
if paper[i][j] != checkboard:
for a in range(3):
for b in range(3):
search(x+a*k//3,y+b*k//3,k//3)
return
if checkboard==-1:
res_1+=1
elif checkboard==0:
res0+=1
elif checkboard==1:
res1+=1
search(0,0,n)
print(res_1)
print(res0)
print(res1)