[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)

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

3954번: Brainf**k 인터프리터

 

 

[ 문제풀이 ]

 

1. 각각의 브라켓의 쌍을 저장할 수 있도록 map을 선언합니다.

 

2. stack을 사용하여 ' [ '를 만나면 stack에 현재 idx를 push 하고, ' ] '를 만나면 stack의 top과 쌍이므로 map [ i ] = stack.top(), map [ stack.top() ] = i를 저장해줍니다.

 

3. 5천만번 반복했을 때 무한 루프 안이거나 프로그램은 항장 종료되어 있기 때문에 5천만 번 반복 후에도 끝나지 않으면 무조건 무한 루프 안입니다.

 

4. 5천 만번 실행 후 한번 더 5천만 번 실행하면서 무한 루프 안이므로 도달한 최대 idx를 max에 저장하고 그에 맞는 쌍을 출력해주면 됩니다.

 

[ 소스코드 ]

#include<iostream>
#include<stack>
#include<map>
#include<cstring>
 
#define M 256
 
using namespace std;
 
unsigned char arr[100000];
char cal[4097];
char input[4097];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int sm, sc, si;
        scanf("%d %d %d", &sm, &sc, &si);
        
        stack<int> s;
        map<int, int> m;
        memset(arr, 0, sizeof(arr));
        scanf("%s", cal);
        scanf("%s", input);
 
        for (int i = 0; i < sc; i++) {
            if (cal[i] == '[') {
                s.push(i);
            }
            if (cal[i] == ']') {
                int temp = s.top();
                s.pop();
                m[temp] = i;
                m[i] = temp;
            }
        }
 
        int cnt = 0;    //연산 횟수
        int cur = 0;    //현재 포이터 위치
        int c = 0;        //현재 연산의 위치
        int in = 0;        //현재 문자열의 위치
        int Max = 0;
 
        while (1) {
            if (cnt > 50000000) {
                Max = max(Max, c);
            }
            if (cal[c] == '+') {
                arr[cur]++;
            }
            else if (cal[c] == '-') {
                arr[cur]--;
            }
            else if (cal[c] == '<') {
                cur--;
                if (cur < 0) {
                    cur = sm - 1;
                }
            }
            else if (cal[c] == '>') {
                cur++;
                if (cur >= sm) {
                    cur = 0;
                }
            }
            else if (cal[c] == '[') {
                if (arr[cur] == 0) {
                    c = m[c];
                }
            }
            else if (cal[c] == ']') {
                if (arr[cur] != 0) {
                    c = m[c];
                }
            }
            else if (cal[c] == ',') {
                if (in < si) {
                    arr[cur] = input[in++];
                }
                else {
                    arr[cur] = 255;
                }
            }
            c++;
            cnt++;
            if (c >= sc) {
                printf("Terminates\n");
                break;
            }
            if (cnt >= 100000000) {
                printf("Loops %d %d\n", m[Max], Max);
                break;
            }
        }
    }
}