dev/algorithm
BOJ / 1992번 / 쿼드트리 [Go][Python3]
crscnt
2020. 12. 29. 21:00
👩🏻💻 문제
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는
www.acmicpc.net
✍🏻 풀이
🎨 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()
728x90