BOJ / 1992번 / 쿼드트리 [Go][Python3]

👩🏻‍💻 문제

1992번: 쿼드트리

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/1992
// 쿼드트리를 문자열로 바꾸는 문제
package main

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

var (
	image  [][]string
	writer *bufio.Writer
)

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

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

	for i := 0; i < n; i++ {
		input, _ := reader.ReadString('\n') // 공백 포함하여 입력 받기 위해 ReadString() 사용
		inputs := strings.Split(input, "")
		image = append(image, inputs)
	}

	quadTree(0, 0, n)
	fmt.Fprintln(writer, "")
}

func quadTree(row, col, n int) {
	first := image[row][col]
	var isComplete bool = true

	for i := row; i < row+n; i++ {
		for j := col; j < col+n; j++ {
			if i == row && j == col {
				continue
			}
			if image[i][j] != first {
				isComplete = false
				break
			}
		}
		if !isComplete {
			break
		}
	}
	if isComplete {
		fmt.Fprint(writer, first)
	} else {
		fmt.Fprint(writer, "(")
		interval := n / 2
		quadTree(row, col, interval)
		quadTree(row, col+interval, interval)
		quadTree(row+interval, col, interval)
		quadTree(row+interval, col+interval, interval)
		fmt.Fprint(writer, ")")
	}
}

🎨 Python3

# https://www.acmicpc.net/problem/1992
# 쿼드트리를 문자열로 바꾸는 문제
import sys

image = []

def quad_tree(row, col, n):
    global image
    first = image[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 image[i][j] != first:
                is_complete = False
                break
        if not is_complete:
            break

    if is_complete:
        print(first, end='')
    else:
        print("(", end='')
        interval = n//2
        quad_tree(row, col, interval)
        quad_tree(row, col+interval, interval)
        quad_tree(row+interval, col, interval)
        quad_tree(row+interval, col+interval, interval)
        print(")", end='')

if __name__ == "__main__":
    n = int(sys.stdin.readline())

    for i in range(n):
        image.append(list(map(int, list(sys.stdin.readline().rstrip()))))
    
    quad_tree(0, 0, n)
    print()