[Silver I] 쿼드트리 - 1992

[Silver I] 쿼드트리 - 1992

인프런 C++ 코딩테스트 강의를 진행하면서 연습 문제로 풀게 된 문제입니다.

제가 진행했을 땐 4개씩 계산해서 답을 구하는 방식이었는데 ' Z ' 형태로 답을 확인하는 부분에서 많이 꼬이게 되더라고요.

한두 시간가량 진행하다가 강사님의 풀이강의를 보고 진행했습니다.

해당 문제를 풀이하실 때 분할정복( Divide and conquer algorithm ) 알고리즘을 사용하셨습니다.

짧게 정리하자면

같은 행동을 하는 함수를 분할해서 진행하고 다시 합쳐서 결과를 확인하는 그런 알고리즘이었습니다.

해당 문제를 풀 때는 재귀함수를 사용해서 0 또는 1을 확인하고 다른 값이 있으면 분할해서 코드를 진행하는 형식으로 풀이가 되었습니다.

[Silver I] 쿼드트리 - 1992 풀이코드

#include <bits/stdc++.h>
using namespace std;

int n;
string s;
char a[70][70];
string answer, lineString;
vector<string> v;

string quard(int y, int x, int size) 
{
	if (size == 1) return string(1, a[y][x]);
	char b = a[y][x];
	string ret = "";
	bool flag = 0;
	for (int i = y; i < y + size; i++)
	{
		for (int j = x; j < x + size; j++)
		{
			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 string(1, a[y][x]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			a[i][j] = s[j];
		}
	}	
	
	cout << quard(0, 0, n) << '\n';
	
	return 0;
}