백준 1992번: 쿼드트리

[문제 링크]

1992번: 쿼드트리

---

https://onlytrying.tistory.com/42

AOJ의 QUADTREE 문제와 유사한 형태의 문제라고 생각한다. 따라서 알고리즘도 비슷하게 구현하였다.

먼저 (startY, startX)좌표를 시작으로 N X N 크기만큼 보드값을 검사한다. 모든 값이 일치한다면 숫자 1 or 0 으로 압축할 수 있다. 값이 일치하지 않다면 N/2 크기의 보드 4개로 나누고 나눠진 보드에 대해 위와 같은 작업을 반복한다.

나눠진 보드들이 반환하는 문자열을 합치고 시작 위치에 '(', 끝 위치에 ')'을 붙여주면 원하는 결과를 출력할 수 있다.

---

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

vector<string> board;

string Solution(int N, int startY, int startX)
{
	bool check = true;
	for (int i = startY; i < startY+N; i++)
	{
		for (int j = startX; j < startX+N; j++)
		{
			if (board[i][j] != board[startY][startX])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check) return string(1,board[startY][startX]);

	int nextN = N / 2;
	string board1 = Solution(nextN, startY, startX);
	string board2 = Solution(nextN, startY, startX + nextN);
	string board3 = Solution(nextN, startY + nextN, startX);
	string board4 = Solution(nextN, startY + nextN, startX + nextN);

	return '(' + board1 + board2 + board3 + board4 + ')';
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		board.push_back(str);
	}
	cout << Solution(N, 0, 0) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day