boj1780-종이의 개수

문제

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

내 풀이 (5816ms)

import sys
input = sys.stdin.readline

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
# print(paper)

minus, zero, plus = 0,0,0
def dq9(x ,y, n):
    global minus, zero, plus
    check = paper[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if check != paper[i][j]:
                dq9(x, y, n//3) # (0,0)
                dq9(x, y+n//3, n//3) # (0,1)
                dq9(x, y+(n//3)*2, n//3) # (0,2)
                dq9(x+n//3, y, n//3) # (1,0)
                dq9(x+n//3, y+n//3, n//3) # (1,1)
                dq9(x+n//3, y+(n//3)*2, n//3)
                dq9(x+(n//3)*2, y, n//3)
                dq9(x+(n//3)*2, y+n//3, n//3)
                dq9(x+(n//3)*2, y+(n//3)*2, n//3) # (2,2)
                return
    
    if check == -1:
        minus += 1
        return
    elif check == 0:
        zero += 1
        return
    else:
        plus +=1
        return

dq9(0,0,N)
print(minus)
print(zero)
print(plus)

쿼드트리와 같은 풀이, 시작 원소 위치와 종이 크기만 다르게 해서 4가 아닌 9번 호출

다른 풀이 (2956ms)

"""1780 종이의 개수"""
import sys

input = sys.stdin.readline
minus_one, zero, one = 0, 0, 0  # -1 종이의 수, 0 종이의 수, 1 종이의 수


def oneColor(n, y, x):
    global minus_one, zero, one

    if n == 1:  # 종이의 크기가 1칸일 때
        if papers[y][x] == "-1":
            minus_one += 1
        elif papers[y][x] == "0":
            zero += 1
        else:
            one += 1
        return

    flag = True  # 현재 종이가 같은 숫자인지 확인
    for j in range(y, y + n):
        if not flag:
            break
        for i in range(x, x + n):
            if papers[y][x] != papers[j][i]:
                flag = False
                break

    if flag:  # 다 같은 숫자일 때
        if papers[y][x] == "-1":
            minus_one += 1
        elif papers[y][x] == "0":
            zero += 1
        else:
            one += 1
        return
    else:  # 다른 숫자일 때
        n //= 3
        # 윗 줄
        oneColor(n, y, x)
        oneColor(n, y, x + n)
        oneColor(n, y, x + n * 2)
        # 중간 줄
        oneColor(n, y + n, x)
        oneColor(n, y + n, x + n)
        oneColor(n, y + n, x + n * 2)
        # 아랫 줄
        oneColor(n, y + n * 2, x)
        oneColor(n, y + n * 2, x + n)
        oneColor(n, y + n * 2, x + n * 2)


num = int(input().rstrip())  # 3의 제곱승으로만 들어옴
papers = [list(input().split()) for _ in range(num)]  # 종이의 상태를 받음
oneColor(num, 0, 0)
print(minus_one)
print(zero)
print(one)

종이 크기 1일때 처리,
종이 모두 같은 숫자인지 확인시 1,2,중 for문에서 모두 True, False 체크 후 break

• 출처 : boj kmj951015님 풀이