BOJ / 2630번 / 색종이 만들기 [Go][Python3]

👩🏻‍💻 문제

2630번: 색종이 만들기

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/2630
// 쿼드트리를 만드는 문제
package main

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

var (
	paper [][]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 := range paper {
		paper[i] = make([]int, n)
	}

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

	blue, white := checkPart(0, 0, n, 0, 0)
	fmt.Fprintln(writer, white)
	fmt.Fprintln(writer, blue)
}

func checkPart(row, col, n, blue, white int) (int, int) {
	first := paper[row][col]
	var isPaper bool = 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 {
				isPaper = false
				break
			}
		}
		if !isPaper {
			break
		}
	}

	if isPaper {
		if first == 1 {
			blue++
		} else {
			white++
		}
		return blue, white
	}

	interval := n / 2
	blue, white = checkPart(row, col, interval, blue, white)
	blue, white = checkPart(row+interval, col, interval, blue, white)
	blue, white = checkPart(row, col+interval, interval, blue, white)
	blue, white = checkPart(row+interval, col+interval, interval, blue, white)
	return blue, white
}

🎨 Python3

# https://www.acmicpc.net/problem/2630
# 쿼드트리를 만드는 문제
import sys

paper = []

def check_part(row, col, n, blue, white):
    global paper
    first = paper[row][col]
    is_paper = 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_paper = False
                break
        if not is_paper:
            break

    if is_paper:
        if first == 1:
            blue += 1
        else:
            white += 1
        return blue, white
    
    interval = n//2
    blue, white = check_part(row, col, interval, blue, white)
    blue, white = check_part(row+interval, col, interval, blue, white)
    blue, white = check_part(row, col+interval, interval, blue, white)
    blue, white = check_part(row+interval, col+interval, interval, blue, white)
    return blue, white

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