1992번 쿼드트리

문제링크 : www.acmicpc.net/problem/1992

1992번: 쿼드트리

---

---

<알고리즘>

  1) getline으로 input받고 하나씩 vector에 저장(숫자 다음에 오는 입력을 getline으로 받기 위해선 개행 때문에 cin.ignore()이 필요하다)

  2) quadTree 알고리즘을 이용해 vector를 4분할하여 병합가능한지 확인

    2-1) 병합 가능하면 answer에 병합한 색깔숫자 입력

    2-2) 병합불가능하면 다시 4분할 하여 병합가능한지 확인

  3) 형식에 맞춰 추가된 answer를 출력

 

 

 

 

메모리 : 2020KB    시간 : 0ms

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string answer = "";
void quadTree(vector<vector<int>> &input, int X, int Y, int size) {
	bool isCombine = true;
	int begin = input[X][Y];
	for (int j = Y; j < Y + size; j++) {
		for (int i = X; i < X + size; i++) {
			if (begin != input[i][j]) {
				isCombine = false;
				break;
			}
		}
		if (isCombine == false) break;
	}

	if (isCombine) {
		answer.append(to_string(begin));
		return;
	}

	size = (int)(size / 2);
	answer.append("(");
	quadTree(input, X, Y, size);
	quadTree(input, X, Y + size, size);
	quadTree(input, X + size, Y, size);
	quadTree(input, X + size, Y + size, size);
	answer.append(")");
}
int main() {
	int N = 0;
	cin >> N;
	cin.ignore();
	vector<vector<int>> input(N,vector<int>(N));
	for (int i = 0; i < N; i++) {
		string temp = "";
		getline(cin, temp);
		for (int j = 0; j < N; j++) {
			input[i][j] = temp[j]-'0';
		}
	}
	quadTree(input, 0, 0, N);
	cout << answer;

	return 0;
}

+) 참고 : chessire.tistory.com/entry/%EC%BF%BC%EB%93%9C%ED%8A%B8%EB%A6%ACQuad-tree

쿼드트리(Quad tree)