https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
또 저번에 푼 2630번과 유사한 문제입니다!
2630번에서는 4등분하면서 나눠진 색종이의 개수를 세는 문제였는데 이번엔 4등분하면서 바로바로 출력하면 됩니다!
이 문제에서 제일 헷갈린 부분이 어느 시점에서 괄호를 출력하느냐 였는데요..
조금만 생각 하면 간단해요!
풀이
2630번 문제처럼 배열을 검사하면서 동일하지않은 색상이나오면 재귀를 이용해서 4등분합니다!
재귀를 시작할때 괄호를 열어줍니다.
그리고 재귀함수 순서도 중요합니다.
시계방향으로 4등분해서 돌 수 있도록 좌표에 신경씁시다.
color가 0이면 0출력, 1이면 출력
재귀가끝나면 return하기전에 괄호를 닫아줍시다!
def paper(a, b, n):
color = field[a][b]
for i in range(a, a+n):
for j in range(b, b+n):
if color != field[i][j]:
print("(", end="")
paper(a, b, n//2)
paper(a, b + n//2, n//2)
paper(a + n//2, b, n//2)
paper(a + n//2, b + n//2, n//2)
print(")", end="")
return
if color == 0:
print("0", end="")
else:
print("1", end="")
n = int(input())
field = [list(map(int,input())) for _ in range(n)]
paper(0, 0, n)
비슷한 문제 참고하세요
https://usagi-coding.tistory.com/3
[백준] 2630번: 색종이 만들기 파이썬
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄
usagi-coding.tistory.com
'PS > 재귀' 카테고리의 다른 글
| [백준] 1991번: 트리순회 파이썬 (3) | 2024.02.28 |
|---|---|
| [백준] 2448번: 별 찍기 - 11 파이썬 (2) | 2024.02.28 |
| [백준] 1780번: 종이의 개수 파이썬 (0) | 2024.02.28 |
| [백준] 2630번: 색종이 만들기 파이썬 (0) | 2024.02.27 |
