Python3
문제
https://www.acmicpc.net/problem/1992
키워드
- 재귀
- 분할 정복
문제 풀이
문제 요구사항
- 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 2차원 배열 영상을 압축한다.
- 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다
- 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.
변수 및 함수 설명
- n : 영상의 크기
- img : 영상 배열 (2차원. 0, 1로만 표현)
- chk :
- x, y :
- quad(x, y, n) : 영상 좌표를 검사하는 재귀함수이다. 매개변수는 좌표와 좌표의 개수이다.
풀이
(입력 및 선언)
- 영상 크기(n)를 입력받는다
- 2차원 영상 배열을 입력 받는다
(쿼드트리 함수)
시작 좌표와 좌표 개수를 매개 변수로 받는다.
아래 사진처럼 처음에 N*N개를 탐색해서 모든 문자열이 0이나 1로 같지 않다면, N/2*N/2, N/4*N/4,..개로 점점 깊이 들어 가면서 탐색한다.
- 시작 좌표의 값을 chk 변수에 넣는다.
- 반복문을 돌면서 시작 좌표의 값과 다른 값을 만나면 chk에 -1을 넣는다.
- 만약 첫 좌표의 데이터 값과 비교해서 같지 않으면, 바로 break로 반복문을 빠져 나오도록 한다.
1) 만약 chk가 -1 이라면,
지금 당장 압축할 수 없기 때문에 더 깊이 들어가서 탐색해야 한다.
- 문제 출력 형식에 따라 괄호를 열어 준다.
- n을 2로 나눈다
- 4등분(왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)으로 나누어 재귀를 돌며 탐색해야 한다.
- quad(x, y, n) -> 왼쪽 위
quad(x, y+n, n) -> 오른쪽 위
quad(x+n, y, n) -> 왼쪽 아래
quad(x+n, y+n, n) -> 오른쪽 아래 아래 그림에서는 x, y가 0, 0이므로 quad(0, 0, 4) quad(0, 4, 4) quad(4, 0, 4) quad(4, 4, 4) 가 될 것이다.
- 재귀를 돌면서 네 등분의 탐색이 끝나면 괄호를 닫는다.
chk 값이 또 -1이라면(압축이 불가능하면) 다시 n을 반으로 쪼개서 재귀 반복..
2) 만약 chk가 1 이라면,
모두 1이라는 뜻으로, 압축값은 1이다. => 1을 출력
3) 만약 chk가 0 이라면,
모두 0이라는 뜻으로, 압축값은 0이다. => 0을 출력
최종 코드
n = int(input())
img = []
for _ in range(n) :
img.append(list(map(int, input())))
def quad(x, y, n) :
chk = img[x][y]
for i in range(x, x+n) :
for j in range(y, y+n) :
if chk != img[i][j] :
chk = -1
break
if chk == -1 :
print('(', end='')
n = n // 2
quad(x, y, n)
quad(x, y+n, n)
quad(x+n, y, n)
quad(x+n, y+n, n)
print(')', end='')
elif chk == 1 :
print(1, end='')
elif chk == 0 :
print(0, end='')
quad(0, 0, n)비슷한 문제
I mean