[ 백준 3954 ] BrainkFuck 인터프리터 (C++)

백준의 Brainfuck인터프리터(3954) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 명령어들에 맞게 명령을 실행하면 되는 문제이다. 각 명령어들을 실행시키는 과정들 부터 알아보자.

명령어 : '-' & '+'

- 현재 가르키고 있는 수를 더하거나 빼는 연산을 하는 명령어이다. 문제의 조건을 잘 보면, "데이터 배열의 값은 0으로

  초기화 되어 있다" 라는 말이 있다. 그리고 초기 포인터는 '0번 Index'를 가르키고 있다고 되어있다.

  즉, 해당 명령어가 나오면, 현재 가르키고 있는 Index의 값을 더하거나 빼주면 되는 명령어이다.

  주의해야 할 점은, 명령어 뒤에 (module 2^8) 이라는 말이 있는데, 2^8으로 모듈러(%) 연산을 한 값을 데이터 배열에

  저장해야 한다는 것을 의미이고, 이는 곧 배열이 가르키는 값의 범위가 0 ~ 255(2^8) 이라는 것을 의미한다.

  따라서, 현재 포인터가 가르키고 있는 배열 값이 '0'인데, '-'명령어가 떨어진다면, -1이 아닌, 255를,

  현재 포인터가 가르키고 있는 배열 값이 255인데, '+'명령어가 떨어진다면, 256이 아닌, 0으로 설정해주면 된다.

명령어 : '<' & '>'

- 현재 가르키고 있는 포인터를 증가시키고 감소시키는 명령어이다. 만약 현재 포인터가 0번째 Index를 가르키고 있는데

  '<' 명령어가 떨어진다면, -1번째 Index를 가르키게 되는데, -1번 Index라는 것은 존재하지 않으므로 가장 마지막

  인덱스로 포인터를 옮겨주면 된다. 반대로, 가장 오른쪽 Index를 가르키고 있을 때, '>' 명령어가 떨어진다면, 배열의 범위를

  벗어나는 Index를 가르키게 되는데, 올바른 접근이 아니므로, 0번째 Index를 포인터가 가르키도록 설정해주면 된다.

명령어 : '[' & ']'

- 루프 명령어이다. 각 괄호가 요구하는 조건을 만족한다면, 짝이 되는 루프로 포인터를 옮겨주면 된다.

   이 부분을 위해서 본인은 입력을 받고 명령어를 실행하기 전에 모든 '['.']' 괄호들에 대한 짝을 미리 설정해 주었다.

   간단하게, 스택의 원리를 이용해서 구현하였다.

   예를 들어서 ' [[[]]] ' 라는 식에 대해서 괄호를 짝지어보자. '[' 괄호가 나오게 되면, 스택에 해당 Index번호를 넣어준다.

   그럼 스택의 상태가 { 0, 1, 2 } 가 될 것이다. ']' 나오게 된다면, 가장 top에 있는 값들부터 하나씩 빼면서 짝을 지어주는 것이다.

   3번 Index 에 있는 ']'에 의해서는 2번이, 4번 Index에 잇는 ']' 에 의해서는 1번이, 5번 Index에 있는 ']'에 의해서는 0번이

   짝이 되는 것이다. (실제로 stack을 구현하거나 사용한 것은 아니고, 단순 배열을 이용해서 구현하였습니다 ! )

   이런 결과를 Loop[] 라는 int형 배열에 저장해 주었다. Loop[a] = b 의 의미는 "a번 index에 있는 괄호가 세트인 괄호는

   b번 index에 있는 괄호입니다" 를 의미한다. 즉, Loop[a] = b 라면, Loop[b] = a 가 된다.

   또한, 이 명령어를 처리할 때 주의해야 할 점이 하나 있다. 바로 무한루프일 경우, 어느 루프 안에서 돌고 있는지를

   파악하기 위해서 "가장 마지막에 방문한 괄호의 인덱스번호"를 저장해 주어야 한다.

   만약, 명령어를 모두 처리했는데, 무한루프가 발생하지 않았다면 상관이 없지만, 무한루프가 발생한 경우라면,

   "가장 마지막에 방문한 괄호"에서 빠져나오고 있지 못하다는 것을 의미하기 때문에 이 부분에 대한 처리가 필요하다.

   따라서, 본인은 ']' 괄호에 대해서, 가장 마지막에 방문한 괄호의 Index번호를 따로 저장해 주었다.

명령어 : '.' & ','

- 출력 명령어인 '.'은 처리할 필요가 없다. 왜냐하면 이 문제의 마지막에 보면 "출력은 무시한다" 라는 말이 있기 때문에

   조건문 조차 걸어주지 않아도 된다.

   ',' 명령어는 문자를 읽어서 배열에 저장해 주어야 한다. 문자를 저장하는 배열에 대한 포인터를 하나 만들어서

   배열에 저장을 해주기만 하면 된다. 해당 포인터가 배열의 끝까지 도달했다면, '255'를 저장해 주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 100000
#define PROCESS_MAX 50000000
#define VALUE_MAX 255
using namespace std;
 
int Sm, Sc, Si;
int Idx, Cmd_Idx, Inp_Idx, Max_Loop_Idx;
int Array[MAX], Loop[MAX], Visit[MAX];
char Command[MAX], Inp[MAX];
bool Cycle;
 
vector<int> G_List;
 
void Initialize()
{
    Idx = Cmd_Idx = Inp_Idx = 0;
    Max_Loop_Idx = -1;
    Cycle = false;
    memset(Array, 0, sizeof(Array));
    memset(Loop, -1, sizeof(Loop));
    memset(Visit, 0, sizeof(Visit));
}
 
void Input()
{
    cin >> Sm >> Sc >> Si;
    for (int i = 0; i < Sc; i++) cin >> Command[i];
    for (int i = 0; i < Si; i++) cin >> Inp[i];
}
 
void Make_Loop_State()
{
    int Stack[MAX] = { 0, };
    int Top_Idx = 0;
    for (int i = 0; i < Sc; i++)
    {
        if (Command[i] == '[') Stack[Top_Idx++] = i;
        else if (Command[i] == ']')
        {
            int Set = Stack[Top_Idx - 1];
            Loop[i] = Set;
            Loop[Set] = i;
            Top_Idx--;
        }
    }
}
 
void Process(char C)
{
    if (C == '-')
    {
        Array[Idx]--;
        if (Array[Idx] < 0) Array[Idx] = VALUE_MAX;
    }
    else if (C == '+')
    {
        Array[Idx]++;
        if (Array[Idx] > VALUE_MAX) Array[Idx] = 0;
    }
    else if (C == '<')
    {
        Idx--;
        if (Idx < 0) Idx = Sm - 1;
    }
    else if (C == '>')
    {
        Idx++;
        if (Idx == Sm) Idx = 0;
    }
    else if (C == '[')
    {
        if (Array[Idx] == 0) Cmd_Idx = Loop[Cmd_Idx];
        
    }
    else if (C == ']')
    {
        if (Array[Idx] != 0)
        {
            if (Cmd_Idx > Max_Loop_Idx) Max_Loop_Idx = Cmd_Idx;
            Cmd_Idx = Loop[Cmd_Idx];
        }
    }
    else if (C == ',')
    {
        if (Inp_Idx >= Si) Array[Idx] = VALUE_MAX;
        else Array[Idx] = Inp[Inp_Idx++];
    }
}
 
void Solution()
{
    Make_Loop_State();
    bool End = false;
    
    for (int i = 0; i < PROCESS_MAX; i++)
    {
        if (Cmd_Idx == Sc)
        {
            End = true;
            break;
        }
 
        char Cmd = Command[Cmd_Idx];
        Process(Cmd);
        Cmd_Idx++;
    }
 
    if (End == true) cout << "Terminates" << endl;
    else cout << "Loops " << Loop[Max_Loop_Idx] << " " << Max_Loop_Idx << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}