[BAEKJOON 1992번] (C++) 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

문제 해결

 

문제의 예제와 아래에 있는 입력과 출력 예제를 보고 나서 문제의 내용을 이해할 수 있었다.

• 입력에 따른 출력형식은 problem을 4개의 subProblem으로 나누고 크기가 1인 가장 하위 subProblem까지 갔을 때 부터 결정되기 시작한다.
• 상위 subProblem의 출력형식은 하위 4개의 subProblem이 통일되어 있는지, 다른지에 따라서 결정되기 때문이다.
• 입력은 항상 2의 제곱수로 이루어지기 때문에 1, 4, 8, 16... 등 크기가 1인 가장 하위 subProblem에서 return한다고 하였을 때 모든 입력을 4개의 subProblem으로 나누어 해결할 수 있다.

 

반례

0000

0101

0000

0101

 

다음과 같은 입력의 경우에는 4개의 subProblem의 return값이 모두 같아서

(0001) 로 출력이 되는 문제가 발생하였는데 문제의 조건에 따르면

((0001)(0001)(0001)(0001)) 이렇게 출력이 되어야 문제가 해결된다.

이를 해결하기 위해

if (compareString(req)&&(req[0]).size()==1)
      return req[0];

다음의 부분을 통하여 각각의 subProblem의 return값이 모두 동일하더라도 size가 1일 때만 하나로 통합되도록 하였다.

 

 

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

#define MAX 65

int N;
int image[MAX][MAX];
string str[MAX];
string answer;

bool compareString(vector<string> str) {
	bool check=true;
	for (int i = 1; i < str.size(); i++) {
		check = str[i - 1].compare(str[i]);
		if (check != 0)
			return false;
	}
	return true;
}

string solution(int h,int x,int y)
{ 
	//h가 1일 때 현재 index를 return
	if (h == 1)
		return to_string(image[x][y]);
	vector<string> req;
	req.push_back(solution(h / 2 ,x, y)); 
	req.push_back(solution(h / 2, x, y+(h / 2)));
	req.push_back(solution(h / 2, x+(h /2) , y));
	req.push_back(solution(h / 2, x+(h / 2), y+(h / 2)));
	
	//abcd가 다 같다면 한 개의 값만 뽑아서 그걸 print하는데 그 때는 ()를 쓰지않음
	//abcd의 값이 다 같은게 아니라면 ()를 쓰고 안에 내용들을 모두 프린트
	if (compareString(req)&&(req[0]).size()==1)
			return req[0];
	else
		return "("+ req[0] + req[1] + req[2] + req[3]+")";
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++){
		string s;
		cin >> s;
		for (int j = 0; j < N; j++)
			image[i][j] = s[j] - '0';
	}
	cout << solution(N, 0, 0);
	return 0;
}

 

결과