[백준 1992] 쿼드트리 (C++/Python)

백준 1780 종이의 개수 https://pinguovo.tistory.com/328 와 풀이는 동일하고 func 앞뒤로 괄호만 넣어주면 된다.

 

---

 

C++)

#include <iostream>
#include <string>
#include <vector>
#define MAX_NUM 64
using namespace std;

string arr[MAX_NUM];
string ans;

bool check(int x, int y, int len) {
	for (int i = x; i < x + len; i++) {
		for (int j = y; j < y + len; j++) {
			if (arr[x][y] != arr[i][j])
				return false;
		}
	}
	return true;
}

void func(int x, int y, int len) {
	if (check(x, y, len)) {
		ans += arr[x][y];
		return;
	}

	ans += "(";

	int temp = len / 2;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++)
			func(x + i * temp, y + j * temp, temp);
	}
	ans += ")";
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	func(0, 0, n);

	cout << ans;

	return 0;
}

 

 

 

 

Python)

import sys
read = sys.stdin.readline

n = int(read().rstrip())
arr = [0] * n
ans = []

def check(x, y, len):
    for i in range(x, x + len):
        for j in range(y, y + len):
            if arr[i][j] != arr[x][y]:
                return False
            
    return True

def func(x, y, len):
    if check(x,y,len):
         ans.append(arr[x][y])
         return
    
    ans.append('(')

    temp = len//2
    for i in range(2):
        for j in range(2):
            func(x + i*temp, y + j * temp, temp)

    ans.append(')')

for i in range(n):
    arr[i] = read().rstrip()

func(0,0,n)

print(''.join(ans))