1992 - 쿼드트리

Coding Test/Baek Joon.

1992 - 쿼드트리

서린이1 2024. 8. 22. 23:25

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

1. 풀이 알고리즘 : DFS(선택), BFS, 분할정복

2. 핵심 아이디어

2-1. 입력값 하나하나를 행렬에 원소로 담기

2-2. (0,0)과 size로부터 시작

2-3. 한번에 4개씩 재귀적으로 호출하며, 각각 재귀는 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래와 size / 2를 계속 매개변수로 담아서, size가 1이 될 때까지 계속 호출한다.

2-4. 문제 조건에 따라서 ret에 계속 String을 담아서 값을 만들어 호출한다.

3. 분할정복 알고리즘의 순차적 흐름 예시

# divide and conqur

# 분할 정복

# n * n 영역의 Matrix를 2 -> 1 -> 3 -> 4 분면 순서(Z 형태로)로 재귀적으로 호출하여 size의 절반씩 계속 쪼갠다.

# 1 1 0 0

# 0 0 0 0

# -> (0)

# 1 1 | 0 0

# 0 0 | 0 0

# -----------

# 0 0 | 0 0

# -> ((1100) 0 0 0 )

# _1_|_1_ | 0 0

# 0 | 0 | 0 0

# --------------------

# 0 0 | 0 0

# -> ((1100)000)

4. 소스 코드

import sys

input = sys.stdin.readline

def quard(y, x, size):
    y = int(y)
    x = int(x)
    size = int(size)
    if size == 1:
        return str(a[y][x]) # 기저 조건(=종료 조건), size가 1일 때는 더 이상 쪼개지지 않는다.
    b = a[y][x] # 1개를 뽑아냄
    ret = ''
    for i in range(y, y + size): # y로 부터 size만큼 쪼갠다
        for j in range(x, x + size): # x로 부터 size만큼 쪼갠다
            if b != a[i][j]:
                ret += '('
                ret += quard(y, x, size / 2) # 왼쪽 위
                ret += quard(y, x + size / 2, size / 2) # 오른쪽 위
                ret += quard(y + size / 2, x, size / 2) # 왼쪽 아래
                ret += quard(y + size / 2, x + size / 2, size / 2) # 오른쪽 아래
                ret += ')'
                return ret
    return str(a[y][x])

n = int(input())
a = [[0] * n for _ in range(n)]
s = ''

for i in range(n):
    s = input()
    for j in range(n):
        a[i][j] = s[j]

print(quard(0, 0, n))

5. 소스 코드의 시각화

# 11 11 00 00

# 00 01 11 00

# 위 영역 결과 : ((110(0101)(0010)

# 11 11 00 00

# 11 11 00 11

# 아래 영역 결과 : 1(0001))

# 합산 : ((110(0101)(0010) + 1(0001))

# 출력 : ((110(0101)(0010)1(0001))