[BOJ][Python]1780번 풀이

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

1780번: 종이의 개수

import sys
ssr = sys.stdin.readline

def sol(r,c,l):
    tmp = p[r][c]
    for i in range(r,r+l):
        for j in range(c,c+l):
            if tmp != p[i][j]:
                le = l//3
                for k in range(3):
                    for h in range(3):
                        sol(r+k*le,c+h*le,le)
                return
    if tmp == -1:
        ans[0] += 1
    elif tmp == 0:
        ans[1] += 1
    else:
        ans[2] += 1

n = int(ssr())
p = [list(map(int, ssr().split())) for _ in range(n)]
ans = [0,0,0]
sol(0,0,n)
print(f'{ans[0]}\n{ans[1]}\n{ans[2]}')

이번 문제는 예전에 풀었던 파란 종이 문제에서 하나가 더 추가된 버전이죠. 딱히 엄청 어려워지진 않았구요. 처음에 풀었을 때는 전에 짰던 것처럼 모조리 탐색하도록 코드를 작성했더니 시간초과가 나서 어떻게든 시간을 줄여보려고 막 수정하던 잔재가 마지막 줄에 남아있습니다.

 

문제 접근 방법은 모든 종이에 적힌 값이 다 똑같아야만 한 장으로 치기 때문에 맨 첫번째 좌표의 값을 저장해두고 탐색을 진행하다가 하나라도 다르면 재귀 호출을 하는 방식으로 작성해봤습니다. 만약 다르지 않다면 모든 값이 tmp와 같다는 뜻이니 tmp에 따라 해당 종이의 갯수를 증가시키는 방법으로 문제를 풀어봤습니다.