07 - 쿼드 트리 QUADTREE

1.

흑백 그림의 string 형태 표현에 대한 규칙설명, string 형태 표현 입력으로 주어졌을 때 그림을 상하반전했을 때의 결과에 대한 string 형태 표현을 출력으로 하는 문제.

 

2,3.

문제에서 트리를 그림으로 굳이 보여준 것에 의문을 갖고 생각해보니 주어진 입력을 트리로 구성만 한다면 x의 자식은 항상 4개고 w,b의 자식은 항상 없으니 루트트리부터 3,4,1,2번째 자식 순회하면 ㅆ가능하다고 생각함.

 

4.

처음엔 재귀로 트리를 구성하려 했지만 내 수준이 너무 떨어져서인지 구현할 수 없었음. string의 최대 길이가 1000이므로 for문으로 돌려도 가능하겠다 싶어서 구현해봄. 

 

1) 첫 인덱스부터 for문을 돌린다면 자식노드로 사용된 노드는 다음에 부모 노드로 사용될 수 있지만, 부모 노드로 사용된 노드는 자식노드로 사용될 수 없다

2) w,b노드는 자식노드를 갖지 않는다.

3) x노드는 항상 4개의 자식노드를 갖는다.

4) x노드의 자식 노드들의 인덱스를 찾을 때 자식 노드의 서브트리에 포함된 x의 개수에 따라 다음 인덱스가 달라지는데 이 규칙이 단순하다. (x 출현 개수 * 4)

 

5.

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

vector<vector<int>> childrenOf;  //트리
vector<bool> visited;
string str;

//트리를 2,3,0,1번째 자식 순서대로 순회함
void callTree(int cur) {
	printf("%c", str[cur]);
	int order[4]{ 2,3,0,1 };
	for (int i = 0; i < 4; i++) {
		if (childrenOf[cur].empty()) return;
		callTree(childrenOf[cur][order[i]]);
	}
}

int main() {
	int tc; 
	cin >> tc;
	while (tc--) {
		cin >> str;
        //--------초기화--------//
		visited.resize(str.size());
		fill(visited.begin(), visited.end(), false);
		childrenOf.resize(str.size());
		for (int i = 0; i < str.size(); i++) {
			childrenOf[i].clear();
		}

		//입력사이즈가 1이면 그냥 그대로 출력, 다음 testcase로
		if (str.size() == 1) {
			cout << str << '\n';
			continue;
		}

		//트리(childrenOf) 구성
		for (int i = 0; i < str.length(); i++) {
			if (visited[i]) continue; //부모노드로 사용된 인덱스, w,b는 다시 볼 필요가 없다.
			int parent = i;
			visited[parent] = true; //부모노드로 사용
			int cur = 1; //parent+1부터 탐색
			for (int j = 0; j < 4; j++) { //4개의 자식에 대해
				if (str[parent + cur] != 'x') { //w,b는 바로 자식노드로 추가.
					childrenOf[parent].push_back(parent + cur);
					visited[parent + cur] = true; //w,b는 다시 봐줄 필요없다
					cur++;
				}
				else if (str[parent + cur] == 'x') { //x인경우
					childrenOf[parent].push_back(parent + cur); //일단 자식노드로 추가
					int cnt = 4; //다음 자식노드는 최소 4칸 후
					for (int k = 1; k <= cnt; k++) { //그 4칸안에 x가 또 들어있으면 탐색범위 늘리고 cnt+=4해줌
						if (str[parent + cur + k] == 'x')cnt += 4;
					}
					cur += cnt + 1;
				}
			}
		}
		callTree(0);
		cout << '\n';
	}
}

6.

O(입력한 문자열의 길이)에 수행되므로 잘 된 것 같다.

 

.후기

괜찮은 발상으로 꽤 빠른 시간에 해결 되서 뿌듯하긴 한데, 트리를 구성하는 코드가 너무 난잡하고 조잡스럽다.

 

재귀로 트리를 구성하려고 했지만 능력이 부족해 구현하지 못했다. 누군가 알려줬으면 좋을텐데 아쉽다.

 

문제에서 (b)트리그림을 주지않았다면 절대로 생각하지 못했을 것 같다.