[Algorithm] Baekjoon 12919번 : A와 B 2

https://www.acmicpc.net/problem/12919

12919번: A와 B 2

string source;
string target;
bool isBreak = false;
 
void DFS(deque<char> str, bool isRightDir)
{
    if (str.size() == source.size())
    {
        bool isCheck = false;
 
        if (isRightDir)
        {
            for (int i = 0; i < source.size(); ++i)
            {
                if (str[i] != source[i])
                {
                    isCheck = true;
                    break;
                }
            }
        }
        else
        {
            for (int i = 0; i < source.size(); ++i)
            {
                if (str[source.size() - 1 - i] != source[i])
                {
                    isCheck = true;
                    break;
                }
            }
        }
 
        if (isCheck) return;
        else
        {
            isBreak = true;
            return;
        }
    }
 
 
    if (isRightDir)
    {
        if (str[str.size() - 1] == 'A')
        {
            str.pop_back();
            DFS(str, isRightDir);
            str.push_back('A');
        }
 
        if (str[0] == 'B')
        {
            str.pop_front();
            DFS(str, !isRightDir);
        }
    }
    else
    {
        if (str[0] == 'A')
        {
            str.pop_front();
            DFS(str, isRightDir);
            str.push_front('A');
        }
 
        if (str[str.size() - 1] == 'B')
        {
            str.pop_back();
            DFS(str, !isRightDir);
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> source >> target;
 
    deque<char> dq;
 
    for (int i = 0; i < target.size(); ++i)
    {
        dq.push_back(target[i]);
    }
 
    DFS(dq, true);
 
    if (isBreak)
    {
        cout << 1;
    }
    else cout << 0;
}
 

문제에선 source에다가 이런저런 작업을 했을 때 target과 일치하는지 알아달라고 했지만, 풀이는 역으로 해야 더 쉽다.

즉 target에서 문제에서 정의한 작업을 역으로 하다가 결국 source와 일치하는지 구하면 된다.

그리고 이 문제를 해결하기위해 deque을 활용했다. 앞,뒤에서 추가하고 빼는 작업이 많기 때문이다.

다른 풀이들을 보면 그냥 reverse로 뒤집어서 하는데, 이 문제에서는 통하지만 문자열 최대길이 n이 매우 커진다면 무조건 시간제한에 걸린다. 최대한 안쓰는게 낫다.

그래서 reverse를 사용하는 대신, 뒤집어야할때마다 isRightDir이라는 변수에 표시만 해두고 앞,뒤로 빼는식으로 구현했다.

 

처음 target에 해당하는 string이 주어졌다고 가정한다.

 

1.

현재 상태의 맨 끝이 'A'라면, 현재상태의 문자열이 되기 직전의 문자열은 마지막에 'A'를 추가하고 작업을 마쳤을 '가능성이 있다'.  정답이 아니라 가능성이 있다는 것이다. 

그렇기 때문에 탐색을 수행할 건데, 이전의 문자열의 상태로 만들기 위해 마지막에 'A'를 빼주고 다시 탐색을 수행한다.

그리고 2번을 수행하기 전에 다시 원형으로 수행시켜야 하기 때문에 뻈던 A를 다시 추가해주고 2번을 수행한다.

 

2. 

현재 상태의 처음이 'B'라면, 현재상태의 문자열이 되기 직전의 문자열은 마지막에 'B'를 추가하고 뒤집은다음 작업을 마쳤을 '가능성'이 있다.

그렇기 때문에 탐색을 수행할 건데, 이전의 문자열의 상태로 만들기 위해 앞에서 B를 빼고 isRightDir = !isRightDir 을 해준다. 뒤집었다는 표현이다.

 

 

위 작업은 isRightDir이 true일때를 설명한 것으로, false라면 수행로직을 반대로 해주면 된다. 

1번같은 경우 맨 끝이 'A'일 때 뭔가를 하는게아니라 맨 처음이 'A'일때로 생각해주면 된다.

2번도 마찬가지고...

또한 정답인지 체크할때도 뒤집어져있는지 여부에 따라(isRightDir) 비교를 다르게 해주면 된다.