알고스팟 알고리즘: 쿼드 트리 뒤집기(QUADTREE) [C++]

문제 출처: https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

1. 코드

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

string reverse(string::iterator& it) {
    char head = *(it++);

    if (head == 'b' || head == 'w')
        return string(1, head);

    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);

    return "x" + lowerLeft + lowerRight + upperLeft + upperRight;
}

int main(void)
{
    int C;
    cin >> C;

    while(C--)
    {
        string picture;
        cin >> picture;

        string::iterator it = picture.begin();
        cout << reverse(it) << endl;
    }
    return 0;
}

(실행)

2. 풀이

string::iterator it = picture.begin();

iterator it을 이용해하여 picture의 시작지점을 가리키게 한다.

string reverse(string::iterator& it) {
    char head = *(it++);

    if (head == 'b' || head == 'w')
        return string(1, head);

    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);

    return "x" + lowerLeft + lowerRight + upperLeft + upperRight;
}

그리고 head에 picture의 첫 번째 부분을 가리키고 그것이 문자 'b' 혹은 'w'라면 문자열로 head를 반환하는데 만약 문자 'x'라면 해당 문자를 분리시키기 위해 reverse 함수를 다시 호출해준다. 그리고 모든 분리가 되면 상하반전이 되어야 하기 때문에 상하반전이되는 순서 대로 더하고 반환하면 된다.

3. 느낀점

아직 분할 정복에 대해 익숙하지 않아서 이 문제를 해결하기 위해 많은 시간을 썼지만 결국 실패했다.

#include <iostream>
#include <string>

using namespace std;

bool isTry(string p)
{
	for (int i = 0; i < p.length(); i++)
		if (p[i] == 'x')
			return true;
	return false;
}

void stringStack(string p, string& arr, int *index)
{
	int xCnt = 0;
	int cnt = *index + 4;
	if (p[*index] == 'x')
	{
		for (int i = *index; i < cnt; i++)
		{
			if (p[i] == 'x')
			{
				xCnt++;
				cnt = i + 5;
			}
		}
	}

	arr = "";

	for (int i = 0; i < xCnt * 4 + 1; i++)
	{
		arr.append(1, p[*index]);
		*index += 1;
	}
}

string solve(string p)
{
	int index = 1;
	
	string arr1, arr2, arr3, arr4;
	stringStack(p, arr1, &index);
	if (arr1.length() > 2) arr1 = solve(arr1);
	stringStack(p, arr2, &index);
	if (arr2.length() > 2) arr2 = solve(arr2);
	stringStack(p, arr3, &index);
	if (arr3.length() > 2) arr3 = solve(arr3);
	stringStack(p, arr4, &index);
	if (arr4.length() > 2) arr4 = solve(arr4);

	return "x" + arr3 + arr4 + arr1 + arr2;
}

int main(void)
{
	int C;
	cin >> C;

	while (C--)
	{
		string picture;
		cin >> picture;

		if(isTry(picture))
			picture = solve(picture);
		cout << picture << endl;
	}
}

위 코드는 실패했던 코드인데 예제는 정상적으로 옳은 정답이 나오지만 막상 제출을 하니 오류가 발생한다. 해결 해볼려고 했지만 결국 시간만 지체되어서 책을 보고 해결할 수 있었다.