문제풀이/BOJ
[Python] BOJ/백준 1992번 쿼드트리
서채리
2022. 7. 6. 17:21
[문제]
https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
[풀이]
재귀 문제.. 분할 정복법 문제
2021.08.11 - [문제풀이/BOJ] - [Python] BOJ/백준 2630번 색종이 만들기
[Python] BOJ/백준 2630번 색종이 만들기
[문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의..
chaewsscode.tistory.com
위 문제랑 거의 똑같다.
[코드]
import sys
def quadtree(x, y, n):
# 픽셀이 1개만 남았을 경우
if n == 1:
return str(image[x][y])
result = []
for i in range(x, x + n):
for j in range(y, y + n):
if image[i][j] != image[x][y]: # 색이 다른 경우 다시 4분할
n = n // 2
result.append('(')
result.extend(quadtree(x, y, n)) # 오른쪽 위
result.extend(quadtree(x, y + n, n)) # 왼쪽 위
result.extend(quadtree(x + n, y, n)) # 오른쪽 아래
result.extend(quadtree(x + n, y + n, n)) # 왼쪽 아래
result.append(')')
return result
return str(image[x][y])
n = int(sys.stdin.readline())
image = [list(map(int, sys.stdin.readline()[:-1])) for _ in range(n)]
print(''.join(quadtree(0, 0, n)))