백준 - Brainf**k 인터프리터(3954)

 문제 링크

스택과 배열을 이용한 단순 구현 문제였다.

주어지는 메모리배열과 명령어, 문자의 길이가 크지 않으므로 해당 길이만큼 선언하고,

명령어에 따라 적절히 조건문을 걸어준다.

무한루프를 찾아야 하므로 가장 중요한 명령어는 '[' 와 ']' 인데, 명령들을 수행하기 전에 미리 

'[' -> ']' , ']' -> '[' 처럼 인덱스를 찾아갈 수 있도록 스택을 이용해 전처리를 해주자.

'[' 을 만나면 스택에 넣고, ']' 을 만나면 스택에서 뺀 '[' 와 link를 연결해 주면 간단히 해결된다.

이제 남은 건 무한루프의 판별인데 ']' 명령을 잘 생각해보면 ']' 를 만났을 때 현재 포인터가 가르키는 수가 

단 한번이라도 0 이라면 그 ']' 는 무한루프가 아니란 걸 알 수 있다.

(다른 곳에서 무한루프를 돌고 있거나 무한루프가 없다.)

따라서 모든 ']' 중에 단 한번도 현재 수가 0 이 나온적이 없던 ']' 와 그 짝 '[' 이 무한루프이다.

#include<iostream>
#include<memory.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 0, 1, -1 };
int mv2[4] = { 1, -1, 0, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int main(void) {
	FIO;

	int t;
	cin >> t;

	while (t--) {
		int sm, sc, si;

		cin >> sm >> sc >> si;

		int* arr = (int*)malloc(sizeof(int) * sm);
		memset(arr, 0, sizeof(unsigned int) * sm);

		int* link = (int*)malloc(sizeof(int) * sc);
		memset(link, 0, sizeof(int) * sc);

		bool* isLoop = (bool*)malloc(sizeof(bool) * sc);
		memset(isLoop, false, sizeof(bool) * sc);

		string order, input;
		cin >> order >> input;

		stack<int> st;

		for (int i = 0; i < sc; i++)
		{
			//'[' 와 ']' 이어주기
			char o = order[i];

			if (o == '[') {
				st.push(i);
			}
			else if (o == ']') {
				int idx = st.top();	st.pop();

				link[i] = idx;
				link[idx] = i;
			}
		}

		int cnt = 0;
		int arr_ptr = 0;
		int order_ptr = 0;
		int input_ptr = 0;

		int cur = 0;

		while(++cnt < 50000000 && order_ptr < sc)
		{
			char o = order[order_ptr++];
			cur = arr[arr_ptr];		//메모리 배열의 현재 수

			switch (o)
			{
			case '+':
				arr[arr_ptr] = (arr[arr_ptr] + 1) % 256;
				break;
			case '-':
				arr[arr_ptr]--;
				if (arr[arr_ptr] < 0)
					arr[arr_ptr] = 255;
				break;
			case '>':
				arr_ptr = (arr_ptr + 1) % sm;
				break;
			case '<':
				arr_ptr--;
				if (arr_ptr < 0)
					arr_ptr = sm - 1;
				break;
			case '[':
				if (arr[arr_ptr] == 0)
					order_ptr = link[order_ptr - 1];
				break;
			case ']':
				if (cur == 0)		
					//단 한번이라도 현재 수가 0 이 나왔었다면 무한루프x
					isLoop[order_ptr - 1] = true;
				if (arr[arr_ptr] != 0)
					order_ptr = link[order_ptr - 1];
				break;
			case '.':
				break;
			case ',':
				if (input_ptr == (int)input.size())
					arr[arr_ptr] = 255;
				else
					arr[arr_ptr] = (int)input[input_ptr++];
				break;
			}
		}

		if (order_ptr >= sc) {
			cout << "Terminates\n";
		}
		else {
			int left, right;

			for (int i = 0; i < sc; i++)
			{
				if (order[i] == ']' && !isLoop[i]) {
					left = link[i];
					right = i;
					break;
				}
			}

			cout << "Loops " << left << " " << right << "\n";
		}

		free(arr);
		free(link);
		free(isLoop);
	}
}