CS/Algorithm 문제

[BaekJoon] 백준 1992번 쿼드트리

[BaekJoon] 백준 1992번 쿼드트리

 

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

 

내코드

 

문제를 이해하는게 제일 어려웠다. 주어진 설명으로 이해가 가지 않았다.

 

다른분들이 써놓은 걸로 문제를 이해 했는데, 배열이 주어지면 모두 같은 수 인지 확인하고 맞으면 해당 수를 넣고, 아니면 4등분해서 각각 같은 수 인지 확인하고.. 반복하는 것이다.

 

간단하게 재귀로 풀었다. 4등분으로 나누고 다시 4등분으로 나누고.. 이렇게 반복하는 과정에서 재귀가 떠올랐다. 다만 재귀로 풀 때에는 조건에 맞게 종료해주는게 중요하다. 특정 조건에 충족했을 때 맞는 값을 반환하는 것이 그나마 제일 까다로웠다.

 

# BaekJoon 1992.py


def solution(arr, pos, x, y, result):
    if pos == 1:
        return result + str(arr[y][x])
    # 모두 같은지 체크
    is_same = True
    value = arr[y][x]
    for i in range(pos):
        for j in range(pos):
            if arr[y+i][x+j] != value:
                is_same = False
    # 같으면
    if is_same:
        return result + str(arr[y][x])
    # 다르면
    elif not is_same:
        result = result + "("
        result = solution(arr, int(pos / 2), x, y, result)
        result = solution(arr, int(pos / 2), int(x + (pos / 2)), y, result)
        result = solution(arr, int(pos / 2), x, int(y + (pos / 2)), result)
        result = solution(arr, int(pos / 2), int(x + (pos / 2)), int(y + (pos / 2)), result)
    result = result + ")"
    return result


N = int(input())
image = [list(map(int, input())) for _ in range(N)]
r = solution(image, N, 0, 0, "")
print(r)

 

 

728x90
반응형