BOJ / 1780번 / 종이의 개수 [Go][Python3]

👩🏻‍💻 문제

1780번: 종이의 개수

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/1780
// 쿼드트리와 비슷한데 4개 대신 9개로 나누는 문제
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	paper      [][]int
	minusCount int
	zeroCount  int
	plusCount  int
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)

	paper = make([][]int, n)
	for i := 0; i < n; i++ {
		paper[i] = make([]int, n)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			fmt.Fscanf(reader, "%d ", &paper[i][j])
		}
	}

	checkPaper(0, 0, n)
	fmt.Fprintln(writer, minusCount)
	fmt.Fprintln(writer, zeroCount)
	fmt.Fprintln(writer, plusCount)
}

func checkPaper(row, col, n int) {
	first := paper[row][col]
	isComplete := true
	for i := row; i < row+n; i++ {
		for j := col; j < col+n; j++ {
			if i == row && j == col {
				continue
			}
			if paper[i][j] != first {
				isComplete = false
				break
			}
		}
		if !isComplete {
			break
		}
	}
	if isComplete {
		switch first {
		case -1:
			minusCount++
		case 0:
			zeroCount++
		case 1:
			plusCount++
		}
		return
	}
	interval := n / 3
	checkPaper(row, col, interval)
	checkPaper(row, col+interval, interval)
	checkPaper(row, col+2*interval, interval)
	checkPaper(row+interval, col, interval)
	checkPaper(row+interval, col+interval, interval)
	checkPaper(row+interval, col+2*interval, interval)
	checkPaper(row+2*interval, col, interval)
	checkPaper(row+2*interval, col+interval, interval)
	checkPaper(row+2*interval, col+2*interval, interval)
}

🎨 Python3

# https://www.acmicpc.net/problem/1780
# 쿼드트리와 비슷한데 4개 대신 9개로 나누는 문제
import sys

paper = []
minus_count = 0
zero_count = 0
plus_count = 0

def check_paper(row, col, n):
    global paper, minus_count, zero_count, plus_count
    first = paper[row][col]
    is_complete = True
    for i in range(row, row+n):
        for j in range(col, col+n):
            if i == row and j == col:
                continue
            if paper[i][j] != first:
                is_complete = False
                break
        if not is_complete:
            break
    if is_complete:
        if first == -1:
            minus_count += 1
        elif first == 0:
            zero_count += 1
        elif first == 1:
            plus_count += 1
        return
    
    interval = n//3
    check_paper(row, col, interval)
    check_paper(row, col+interval, interval)
    check_paper(row, col+2*interval, interval)
    check_paper(row+interval, col, interval)
    check_paper(row+interval, col+interval, interval)
    check_paper(row+interval, col+2*interval, interval)
    check_paper(row+2*interval, col, interval)
    check_paper(row+2*interval, col+interval, interval)
    check_paper(row+2*interval, col+2*interval, interval)

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    for i in range(n):
        paper.append(list(map(int, sys.stdin.readline().split())))

    check_paper(0, 0, n)
    print(minus_count)
    print(zero_count)
    print(plus_count)