테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 쿼드트리 ======

===== 풀이 =====
  * 그냥 시키는대로 구현하면 되는 문제.
  * 쿼드트리로 압축한 데이터의 크기만을 구하는 문제였던 [[ps:problems:boj:2630]]에서는 반복으로 구현했지만, 여기에서는 재귀를 써서 구현했다. 
  * 시간복잡도는 N*N + (N/2 * N/2) + (N/4 * N/4) + … + (1 * 1) = (N^2)/3 = O(N^2) 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1992. 쿼드트리".

- Problem link: https://www.acmicpc.net/problem/1992
- Solution link: http://www.teferi.net/ps/problems/boj/1992
"""


def solve(data, r, c, size):
    if size == 1:
        return data[r][c]
    else:
        size //= 2
        quad = ''.join([solve(data, r, c, size),
                        solve(data, r, c + size, size),
                        solve(data, r + size, c, size),
                        solve(data, r + size, c + size, size)])
        if quad == '1111':
            return '1'
        elif quad == '0000':
            return '0'
        else:
            return f'({quad})'


def main():
    N = int(input())
    data = [input() for _ in range(N)]

    print(solve(data, 0, 0, N))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_1}}