백준 알고리즘 1992 (쿼드트리) - python

백준 알고리즘 1992 (쿼드트리) - python

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

1992번: 쿼드트리

 

분할 정복 문제인데, 주의할 점이 몇 가지 있다.

1. 4분할에 대한 4분면의 해당 순서

2. 시작 '(' 의 괄호를 넣는 위치

    - 한 사분면 전체가 같지 않다는 것을 파악하면 대입

    - 만약 입력 전체가 1이면 '(1)'이 아니라 그냥 '1'이다.

3. 끝 ')'의 괄호를 넣는 위치

    - 한 사분면이 끝날 때 대입

 

[예시 입력]

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

[예시 출력]

((110(0101))(0010)1(0001))

예시로 제시해 준 결과를 한 눈에 보이도록 정리하면 아래와 같다.

 

[문제 풀이]

1. 분할 정복을 위한 dfs 함수 생성

2. 탈출 조건 : 한 사분면이 모두 같거나 한 사분면에 숫자가 하나만 존재할 때

3. 한 사분면을 검사하는 함수 생성

4. 한 사분면 전체가 같지 않다는 것을 파악하면 '(' 대입과 함께 분할 정복 시작

5. 사분면의 시작 점과 크기를 4개로 나누어 지정

6. 한 사분면이 끝나는 시점에 ')' 대입

 

import sys
N = int(sys.stdin.readline())
_map = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
result = ''

def is_block_all_same(start_x, start_y, N):
    num = _map[start_x][start_y]
    for i in range(start_x, start_x + N):
        for j in range(start_y, start_y + N):
            if num != _map[i][j]:  # 한 개라도 틀리면
                return False, _map[start_x][start_y]
    return True, _map[start_x][start_y]

def dfs(depth, start_x, start_y, N):
    global result
    flag, block = is_block_all_same(start_x, start_y, N)
    # 한 사분면이 같거나 한 사분면에 숫자가 하나만 존재할 때 탈출
    if flag or N // 2 == 0:
        result += str(block)
        return
    result += '('
    dfs(depth+1, start_x, start_y, N // 2)  # 1사분면
    dfs(depth+1, start_x, start_y + N // 2, N // 2)  # 2사분면
    dfs(depth+1, start_x + N // 2, start_y, N // 2)  # 3사분면
    dfs(depth+1, start_x + N // 2, start_y + N // 2, N // 2)  # 4사분면
    result += ')'
    return

dfs(0, 0, 0, N)
print(result)