[백준] 1992번 : 쿼드트리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/1992

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이전 "2630번 : 색종이 만들기" 문제와 매우 유사한 문제이다.

0과 1로만 이루어진 영상을 각 4개의 영역으로 나누어 해당 구역을 쿼드 트리 구조를 이용하여 압축하는 문제이다.

4개의 영역을 압축하여 그 결과를 차례대로 괄호 안에 묶어서 표시한다.

2630번 문제와 유사하므로 동일하게 분할 정복 알고리즘으로 해결할 수 있다.

해당 문제도 마찬가지로 나눈 4개의 영역이 하나의 값으로 압축되지 않는다면 다시 4개의 영역으로 나누어 압축 해야 하므로 분할 정복 알고리즘을 재귀적으로 사용하여 해결하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 영상의 크기를 입력받는다. N = int(sys.stdin.readline())
3. 영상을 2차원 리스트로 저장해 줄 빈 리스트를 생성한다. video = []
4. 영상의 크기만큼 반복하며 for _ in range(N)
   1. 각 행별 정보를 리스트로 입력받아 st = sys.stdin.readline().rstrip()
   2. 개별 문자로 분리해 정수형으로 저장된 리스트로 구성하고 li = list(int(i) for i in st)
   3. 리스트를 영상 배열에 추가한다. video.append(li)
5. 해당 영역이 어떤 값으로 구성되어 있는지 판별하는 함수를 정의한다. def check(video)
   1. 해당 영역에 있는 0의 개수를 저장할 변수를 생성하고 초기화한다. count_0 = 0
   2. 해당 영역에 있는 1의 개수를 저장할 변수를 생성하고 초기화한다. count_1 = 0
   3. 판별할 영역의 각 행을 차례대로 불러와 for row in video
      1. 각 행의 0의 개수를 세어 더해주고 count_0 += row.count(0)
      2. 1의 개수를 세어 더해준다. count_1 += row.count(1)
   4. 만약 0의 개수가 0개이면 해당 영역은 모두 1로만 되어 있으므로 1로 압축한다. if (count_0 == 0): return '1'
   5. 만약 1의 개수가 0개이면 해당 영역은 모두 0으로만 되어 있으므로 0으로 압축한다. elif (count_1 == 0): return '0'
   6. 반면에 0과 1의 개수가 모두 0이 아니면 해당 영역은 0과 1이 섞여있는 영역이므로 False를 반환해 준다. else: return False
6. 해당 영상을 4개의 영역으로 나누는 함수를 정의한다. def divide(N, video)
   1. 새로운 영역의 한 변의 길이를 저장한다. size = N // 2
   2. 영상을 각 4개의 영역으로 나눠 저장한다. v_1 = [row[ : size] for row in video[ : size]]
   3. v_2 = [row[size : ] for row in video[ : size]]
   4. v_3 = [row[ : size] for row in video[size : ]]
   5. v_4 = [row[size : ] for row in video[size : ]]
   6. 나눈 4개의 영역을 한 리스트로 묶어 저장해 둔다. new_video = [v_1, v_2, v_3, v_4]
   7. 나눈 4개의 영역을 각각 하나씩 불러오며 for v in new_video
      1. 해당 영역이 어떤 값으로 이루어졌는지 판별한다. result = check(v)
      2. 만약 해당 영역이 0과 1이 섞인 영역이라면 if (not result)
         1. 정답 리스트에 '('를 추가하고 answer.append('(')
         2. 해당 영역을 다시 나누어 결과를 저장한 후 divide(size, v)
         3. 정답 리스트에 ')'를 추가한다. answer.append(')')
      3. 반면에 해당 영역이 0으로만 되어 있거나, 1로만 되어 있는 영역이라면 판별한 값을 정답 리스트에 추가한다. else: answer.append(result)
7. 영상을 압축한 결과를 저장할 리스트를 생성한다. answer = []
8. 처음 영상이 0으로만 되어 있거나, 1로만 되어 있을 수 있으므로 해당 영상의 값을 판별한다.
9. 만약 해당 영상이 0과 1이 섞인 영상이라면 if (not check(video))
   1. 정답 리스트에 '('를 추가하고 answer.append('(')
   2. 해당 영상을 나누어 결과를 저장한 후 divide(N, video)
   3. 정답 리스트에 ')'를 추가한다. answer.append(')')
10. 반면에 해당 영상이 0으로만 되어 있거나, 1로만 되어 있는 영상이라면 판별한 값을 정답 리스트에 추가한다. else: answer.append(check(video))
11. 정답 리스트에 있는 모든 값을 하나의 문자열로 합쳐 출력한다. print(''.join(answer))

3. 소스코드

import sys

N = int(sys.stdin.readline())

video = []
for _ in range(N):
    st = sys.stdin.readline().rstrip()
    li = list(int(i) for i in st)
    video.append(li)

def check(video):
    count_0 = 0
    count_1 = 0

    for row in video:
        count_0 += row.count(0)
        count_1 += row.count(1)

    if (count_0 == 0):
        return '1'
    elif (count_1 == 0):
        return '0'
    else:
        return False

def divide(N, video):
    size = N // 2

    v_1 = [row[ : size] for row in video[ : size]]
    v_2 = [row[size : ] for row in video[ : size]]
    v_3 = [row[ : size] for row in video[size : ]]
    v_4 = [row[size : ] for row in video[size : ]]

    new_video = [v_1, v_2, v_3, v_4]

    for v in new_video:
        result = check(v)
        if (not result):
            answer.append('(')
            divide(size, v)
            answer.append(')')
        else:
            answer.append(result)

answer = []
if (not check(video)):
    answer.append('(')
    divide(N, video)
    answer.append(')')
else:
    answer.append(check(video))

print(''.join(answer))