20.07.28 개발일지 - 무어기계

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

3300번: 무어 기계

무어 머신을 입력받고 이를 그래프로 표현하는 부분을 구상하였습니다.

원래는 이대로 끝내려 했지만 4일에 한번 있는 저녁 운동 없는 날이기도 하고,
요즘 알고리즘을 열심히 안한 느낌도 있어서 구현까지 해보았습니다.

테스트 결과 왠만한 경우에서 잘 작동하고 있습니다.

 

#include <iostream>
#include <sstream>
#include <string>   
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int FindFormerNode(const vector<int>& Heights, const int& height, const int& index)
{
    for (int i = index - 1; i >= 0; --i)
    {
        if (Heights[i] < height)
        {
            return i;
        }
    }
    return 0;
}

vector<int> FindFormerNodes(const vector<vector<int>>& Nodes, const vector<int>& Heights, const int& height, const int& index, const int& gap)
{
    vector<int> ret;
    for (int i = index - 1; i >= 0; --i)
    {
        if (height == Heights[i])
        {
            break;;
        }
        if (!Nodes[i].empty())
        {
            continue;
        }
        if (height - Heights[i] >= gap)
        {
            ret.push_back(i);
        }
    }
    return ret;
}

int main()
{
    int testtime = 0;
    
    cin >> testtime;

    while (testtime-- > 0)
    {
        string machine, testcase;

        char result = '!', special = 0;
        int gap = 0, height = 0, index = 0;

        vector<char> Spells;
        vector<int> Indices, Heights;
        vector<vector<int>> Nodes;

        cin >> machine >> testcase;

        for (const auto& iter : machine)
        {
            if (iter == '(')
            {
                ++height;
                ++gap;
                special = iter;
                continue;
            }
            if (iter == ')')
            {
                --height;
                --gap;
                special = iter;
                continue;
            }
            if (iter == '|')
            {
                special = iter;
                continue;
            }
            switch (special)
            {
            case '|':
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                Nodes[FindFormerNode(Heights, height, index)].push_back(index);
                Indices.push_back(index++);
            }
                break;
            case ')':
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                auto Former = FindFormerNodes(Nodes, Heights, height, index, gap);
                for (const auto& i : Former)
                {
                    Nodes[i].push_back(index);
                }
                Indices.push_back(index++);
                gap = 0;
            }
                break;
            default:
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                if (Nodes.size() > 1)
                {
                    Nodes[index - 1].push_back(index);
                }
                Indices.push_back(index++);
                gap = 0;
            }
                break;
            }
            special = iter;
        }
        cout << endl;

        
        cout << result << endl;
    }
    return 0;
}

 

우선 Special Character 처리입니다.

흐름에 영향을 주는 Character는 (, |, ) 3가지가 있습니다.

 

( 문자는 입력 시 현재 높이와 이전 Node로부터의 높이가 1씩 올라갑니다.

 

) 문자는 반대로 입력 시 현재 높이와 이전 Node로부터의 높이가 1씩 내려갑니다.

 

| 문자는 입력 자체로는 영향이 없습니다.

 

이 특수 문자는 자체가 입력될 때는 아무 행동도 하지 않습니다.

그렇기에 Special이라는 메모리에 따로 저장을 합니다.

 

그리고 위 3 문자가 아닌 다른 문자 입력 시 Special 문자에 따라 흐름이 달라지게 됩니다.

 

( 문자 입력 시에는 앞 Node에 자신의 Index를 추가합니다.

하지만 이는 일반 문자도 동일하기에 따로 처리하지 않고 있습니다.

 

| 문자는 입력 시 자신의 선행 Node를 찾아 그 Node에 Index를 추가합니다.

선행 Node는 자신의 앞에 있는 Index 중 자신의 높이보다 낮은 높이를 지닌 첫번째 Node입니다.

 

) 문자는 입력 시 자신의 선행 Node들을 찾아 그 Node들에 Index를 추가합니다.

이 때 선행 Node는 | 문자와 다르게 검색합니다.

 

| 문자는 선행 Node가 자기 자신과 연속적으로 붙어 있기에 단순 비교로 가능합니다.

하지만 )문자는 모든 Node를 검색해야 하기에 단순 비교로는 다른 군(| 문자 앞의 문자들)을 구분할 수 없게 됩니다.

이 때문에 이전 Node와의 거리인 gap이 추가된 것입니다.

 

먼저 비교 Node와 자신의 높이가 동일하다면 함수를 마칩니다.

이는 이미 ) 범위 안의 연산이 끝났다는 것을 의미하기 때문입니다.

 

또한 비교 Node가 이미 다른 Index 값을 가지고 있으면 다음 연산으로 넘어갑니다.

) 연산은 연속적인 Node의 리스트 중 꼬리에만 붙습니다.

Node가 이미 다른 Index 값을 가지고 있다면 이는 꼬리가 아니라는 의미입니다.

 

위 두가지 경우를 제외하고, 두 Node의 높이 차가 gap보다 크거나 같을 경우 Return 할 Vector에 값을 추가합니다.

 

여기서 중요한 조건은 두번째입니다.

그 이유는 세번째 조건은 같은 군에서 이미 Node 값이 있는 것들도 옳다고 판단하기 때문입니다.

그리고 그 조건을 먼저 제거해주는 것이 두번째 조건입니다.

 

세번째 조건은 금새 다다를 수 있지만, 두번째 조건이 없다면 한참을 해맬 것입니다.

 

여기까지 짜놓고 끝까지 작성하지 않은 이유는
아직 이 Graph를 효율적으로 순회해서 탐색하는 방법은 명확하게 정하지 못했기 때문입니다.

일단 시도해보는 방법도 있지만,
이 문제를 풀어오면서 생각을 오래해서 정리를 하는 것이 좋은 답을 도출한다는 것을 느꼈습니다.

이 느낌을 더 느껴보고 싶습니다.

 

그래서 내일 Graph 순회 방법을 고려해보고자 합니다.

일단 가지고 있는 아이디어는 Spells 길이와 동일한 Vector<int>iterator를 두는 것입니다.

Graph를 한 방향으로만 가는 것이 아니라 다른 방향으로도 순회해야 하는데,

재귀문은 메모리 문제가 발생할 것 같기에 이런 방법을 사용해야 할 것 같습니다.

 

        cout << "Indices:\t";
        for (const auto& i : Indices)
        {
            cout << i << " ";
        }
        cout << endl;
        cout << "Spells:\t\t";
        for (const auto& i : Spells)
        {
            cout << i << " ";
        }
        cout << endl;
        cout << "Heights:\t";
        for (const auto& i : Heights)
        {
            cout << i << " ";
        }
        cout << endl;
        for (const auto& i : Nodes)
        {
            for (const auto& j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }