[시뮬레이션] 백준 3954 Brainf**k 인터프리터 C++

※ 문제

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

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

문제가 이해가 안 되어서 다른 분들의 질문과 코드를 참고하였다. 그럼에도 불구하고 이해하는 데 시간이 굉장히 오래 걸렸다.

 

※ 풀이

1) modulo 2^8의 의미

molulo 2^8은 2^8인 256을 나누는 수로 하는 나머지 연산으로, 256 이상인 수는 256으로 나머지 연산을 한다. 즉 모든 수를 0부터 255 사이의 수로 만든다.

예를 들어 +연산으로 배열 값인 255를 증가시키면 256이 되므로 256 % 256 = 0 연산을 진행해 0을 저장한다. 이 연산 때문에 모든 배열 값이 오버플로우나 언더플로우가 발생하지 않는다.

 

2) 배열 인덱스 초과 에러

포인터를 양옆으로 움직이다보면 배열 인덱스 초과가 날 텐데 이에 대한 설명이 어디 있나 찾다가 헤맸는데, 중간에 인덱스 처리에 관한 설명을 뒤늦게 발견했고, 구현은 어렵지 않았다.

 

포인터를 왼쪽이나 오른쪽으로 움직일 때, 데이터 배열의 범위를 넘어간다면, 반대쪽으로 넘어가게 된다. 즉, 포인터가 0을 가리킬 때, 1을 감소시킨다면, 배열의 크기 - 1번째를 가리키게 된다.

 

2) 명령어를 실행하기 전부터 괄호 인덱스들을 짝지어 map이나 배열에 저장한다.

매번 짝이 맞는 괄호를 찾으면 시간초과에 걸리므로, 미리 스택을 활용해 짝이 맞는 괄호를 찾는다.

주의할 점은 한쪽 괄호 인덱스로 다른쪽 괄호 인덱스 값을 얻을 수 있도록 저장해야 접근하기 편리하다.

 

3) 명령어 수행 횟수가 50,000,000를 초과했음에도 종료하지 못했다면 무조건 무한 루프 안에 있는 경우이다.

당연한 이야기가 왜 써있지 생각했더니, 50,000,000번 이상 수행했는데 종료되지 않았다면 무조건 무한 루프로 생각하라는 의미였다.

 

프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다.

 

4) 무한 루프 안에 있는 경우, 무한 루프 한 번 돌 때 인덱스의 최솟값을 저장한다.

다른 분들의 코드를 참고하면 명령어를 최대 50,000,000 + 50,000,000 = 100,000,000번 실행시키는 것을 볼 수 있는데, 명령어 최대 수행 횟수는 50,000,000에도 이의 2배나 되는 횟수를 실행시키는지 처음에 이해하지 못했다. 처음에는 무한 루프에서 실행하는 명령어의 횟수는 명령어 수행 횟수에 들어가지 않는 건가 싶었는데, 이미 무한 루프임을 확인한 후 무한 루프 인덱스를 확인하기 위해 추가적으로 실행하는 명령어들 이었다. 무한 루프임에도 50,000,000 이하의 명령어 수행으로 루프를 최소 한 번 이상 돌 수 있다는 조건이 주어졌기 때문에 최대 50,000,000 만큼만 추가적으로 명령어들을 실행하면 무한 루프의 시작 인덱스를 알 수 있다. 무한 루프의 시작 인덱스는 추가적으로 명령어들을 실행할 때 명령어 인덱스의 최솟값으로 알 수 있다. 시작 인덱스를 알았으면 위에서 짝지어 저장한 map이나 괄호 배열로 끝 인덱스도 알 수 있다.

#include <bits/stdc++.h>

using namespace std;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	for (int test_case = 0; test_case < t; test_case++) {
		int m, c, i;
		cin >> m >> c >> i;

		char brainf[4097], scan[4097], mem[100000]; // 명령어, 입력, 메모리 배열
		cin >> brainf >> scan;

		memset(mem, 0, sizeof(mem));

		// 괄호 인덱스 저장하기(left[왼쪽 괄호 인덱스] = 오른쪽 괄호 인덱스)
		stack<int> st;
		int left[4097], right[4097];
		for (int j = 0; j < c; j++) {
			if (brainf[j] == '[') st.push(j);
			else if (brainf[j] == ']') {
				left[st.top()] = j;
				right[j] = st.top();
				st.pop();
			}
		}

		int runTime = 0; // 명령어 실행 횟수
		int b = 0; // brainf 프로그램 명령어 인덱스
		int s = 0; // 문자 하나씩 읽기
		int p = 0; // 메모리 포인터
		int loopStart = INT_MAX; // 최댓값 저장
		
		while(true) {
			switch(brainf[b]) {
				case '+':
					mem[p] += 1;
					if (mem[p] == (1 << 8)) mem[p] = 0; // modulo 2^8
					break;
				case '-':
					mem[p] -= 1;
					if (mem[p] == -1) mem[p] = (1 << 8) - 1;
					break;
				case '<':
					p--;
					if (p == -1) p = m - 1; // 인덱스 처리
					break;
				case '>':
					p++;
					if (p == m) p = 0;
					break;
				case '[':
					if (mem[p] == 0) b = left[b];
					break;
				case ']':
					if (mem[p] != 0) b = right[b];
					break;
				case ',':
					if (scan[s] == '\0') mem[p] = 255;
					else {
						mem[p] = scan[s];
						s++;
					}
					break;
			}

			b++;
			runTime++;
			if (b == c) {
				cout << "Terminates\n"; // 종료
				break;
			}

			// (50000000번 실행 후 종료 못했으면 무한 루프 무조건 존재)
			if (runTime >= 50000000) loopStart = min(loopStart, b - 1); // b 증가시키기 전에 루프 인덱스의 최솟값 저장
			if (runTime >= 100000000) {
				cout << "Loops " << loopStart << " " << left[loopStart] << "\n"; // 무한 루프 인덱스 확인하기 위한 최대 시간 실행
				break;
			}
		}
	}
}