Algorithm PS/BOJ
[BOJ] 1780 / 종이의 개수 / Python 파이썬
migrationArc
2021. 6. 22. 22:58
[BOJ] 1780 / 종이의 개수 / Python 파이썬
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
www.acmicpc.net
풀이
[BOJ] 1992 / 쿼드트리 문제의 심화 문제이다.
쿼드트리에서는 주어진 2차원 배열을 2x2 분할 하였다면, 이번 문제에서는 3x3으로 분할 하여 해결 하였다.
import sys
input = sys.stdin.readline
N = int(input())
maps = []
for _ in range(N):
maps.append(input().split())
cntDic = {"-1": 0, "0": 0, "1": 0}
def DFS(y, x, n):
if n == 1:
cntDic[maps[y][x]] += 1
return
for i in range(y, y+n):
for j in range(x, x+n):
if maps[y][x] != maps[i][j]:
DFS(y, x, n//3)
DFS(y, x+n//3, n//3)
DFS(y, x+(n//3*2), n//3)
DFS(y+n//3, x, n//3)
DFS(y+n//3, x+n//3, n//3)
DFS(y+n//3, x+(n//3*2), n//3)
DFS(y+(n//3*2), x, n//3)
DFS(y+(n//3*2), x+n//3, n//3)
DFS(y+(n//3*2), x+(n//3*2), n//3)
return
cntDic[maps[y][x]] += 1
return
DFS(0, 0, N)
print(cntDic["-1"])
print(cntDic["0"])
print(cntDic["1"])