백준,BOJ ) 3954. Brainf**k 인터프리터 ( C / C++ ) (`21.3.25 수정)

1. 문제 링크

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

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

2. 문제 개요

 Brainfuck 프로그램이 주어졌을 때, 프로그램이 끝나는지, 무한 루프에 빠지는지 검사하는 프로그램 만들기.

 

3. 문제 힌트!! (힌트 보고 다시 풀어보세요)

무한 Loop 찾을 때 : 들어온 적은 있지만 나간 적은 없다.

 

 

※ 질문 검색란에 있는 반례

(1)

1

10 9 3

+[-[><]-]

qwe

 

와 같은 경우를 보면 가장 바깥 루프를 1번 돌고 안쪽 루프를 무한 번 돈다.

즉, 가장 바깥쪽 루프를 찾아내면 안 됨!!!!

 

(2)

1

1 9 1
++[[++]+]
a

이 예제도 한번 다 돈 뒤 안의 무한루프에 빠진다.

 

문제를 따라, 일단 5천만 번 돌려보고 Terminate가 되지 않는다면 그 프로그램은 무한루프이다.

무한루프 안에 유한루프가 있을 수 있기 때문에, 단순히 끝난 지점에서 가장 가까운 루프 or 가장 먼 루프를 찾는 것은 답이 될 수 없다.

 

4. 문제 풀이

 우선 - + < > [ ]. , 의 기능을 하나하나 다 구현하는 문제입니다. (이게 궁금한 게 아닐겁니다. loop 관련해서 밑에 적었습니다.)

메모리 배열 mem [mptr]을 선언합니다. mem [mptr]은 mptr이 가리키는 곳의 값, mptr은 포인터를 나타냅니다.

 

 '-', '+'명령이 들어오면 포인터가 가리키는 숫자의 값을 1 증가, 감소시킵니다. 여기서 modulo 2^8로(0~255)

되어있기 때문에 255+1 = 0, 0 - 1 = 255로 되도록 값을 수정해줍니다.

 

 '<', '>' 명령이 들어오면 mptr의 값을 1 증가, 감소시킵니다. 이 또한 각 테스트 케이스에서 들어오는 memory size에 맞춰서, Maxsize +1 = 0, 0 - 1 = Maxsize가 되도록 값을 수정해줍니다.

 

'[', ']' 각 괄호는 만날 때마다 짝을 구하면 '시간 초과'가 발생합니다.

입력받을 때 O(N)의 시간 복잡도로 짝의 Index를 저장하는 배열을 만들어 기록해둡시다.

Stack에 '[' push시 '['의 Index를 삽입합니다.

']'를 만났을 때 pop 함과 동시에 현재 iterator에는 '['의 index를, '['의 index에는 현재 iterator를 대입해둡니다.

 

'.'출력은 무시하라고 했으니 cptr변수만 증가시켜줍니다.

 

', ' 문자 값을 읽고 메모리에 저장합니다. 문자열을 모두 읽었을 경우(EOF)에는 계속 255를 저장하도록 합니다.

 

 

<Loop 판별>

우선 5천만번을 실행해 봅시다. 그전에 끝난다면 Terminate를 출력하고 다음 케이스로 넘어갑니다.

 

why?

문제에 나온 내용대로, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 미만입니다. 그래서 5천만 번을 실행했는데 끝나지 않으면 일단 무한루프 속에 들어가 있습니다.(문제의 조건이 무한루프는 적어도 한 번 실행된다고 했음.)

 

그런데 주의할 점이, 무한루프 속에 유한루프가 있을 수 있습니다. 딱 끝나는 타이밍이 무한루프 속의 유한 루프일 수 있습니다. 제가 (3)에서 예를 들었던 것처럼 이 이유 때문에 단순히 5천만 번 실행 후 가장 가까운 루프를 찾으면 안 되는 것입니다.  무한루프 안 이라면 다시는 밖으로 나갈 수 없습니다. 그래서 또 50,000,000번을 실행해 봅니다.

 

이때, 지금 코드를 가리키는 포인터(배열의 index)를 cptr이라고 했을 때, 50,000,001 ~ 100,000,000번 동안 포인터가 움직였던 범위를 기록합니다. (최솟값을 mincptr, 최댓값을 maxcptr이라고 했습니다.)

 

실제 무한루프에서 무한루프의 ']'를 만났을 때, 무한루프의 '['의 바로 다음 index로 이동하게 되고, 이게 범위의 최솟값이 됩니다.

그래서 100,000,000번을 실행하고 난 뒤, 여전히 무한루프를 빠져나오지 못했을 거고, 무한루프를 적어도 한 번 실행했을 것이기 때문에, mincptr - 1 이 무한루프의 '['가 될 것 이고 maxcptr이 ']'가 됩니다.

 

크게 보면 일단 무한루프 속으로 확실히 들어온 뒤, 범위를 기록해서(이때, 무한루프를 적어도 1번 순회했다는 것이 보장되어야 함.) 무한루프의 정확한 위치를 파악함.

 

5. 코드

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

int main(void)
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		//program data
		int mem[100000] = { 0 };
		char code[4096] = { 0 };
		char inputdata[4096] = { 0 };
		int cptr = 0, wptr = 0, mptr = 0;
		

		int memsize, codelen, inputlen;
		scanf("%d %d %d", &memsize, &codelen, &inputlen);
		scanf("%s", code);
		scanf("%s", inputdata);

		//짝 맞는 괄호 찾아두기
		int braket_left[4096], braket_right[4096] = { 0 };
		//braket_left에는 짝에 맞는 ']'가 있음.
		stack<int> s;
		for (int i = 0; i < codelen; ++i) {
			if (code[i] == '[') 
				s.push(i);
			
			if (code[i] == ']') {
				braket_right[i] = s.top();
				braket_left[s.top()] = i;
				s.pop();
			}
		}
		
		int runtime = 0;
		int mincptr, maxcptr;

		while (cptr < codelen)
		{
			if (runtime == 50000000) {
				mincptr = maxcptr = cptr;
			}
			if (runtime >= 100000000) {
				printf("Loops %d %d\n", mincptr - 1, maxcptr);
				break;
			}
			//=================   start  ================

			if (code[cptr] == '-')
			{
				mem[mptr]--;
				if (mem[mptr] < 0)
					mem[mptr] = 255;
				cptr++;
			}
			else if (code[cptr] == '+')
			{
				mem[mptr]++;
				if (mem[mptr] > 255)
					mem[mptr] = 0;
				cptr++;
			}
			else if (code[cptr] == '<')
			{
				mptr--;
				if (mptr < 0)
					mptr = memsize - 1;
				cptr++;
			}
			else if (code[cptr] == '>')
			{
				mptr++;
				if (mptr > memsize - 1)
					mptr = 0;
				cptr++;
			}
			else if (code[cptr] == '[')
			{
				//lets find ']'
				if (mem[mptr] == 0) 
					cptr = braket_left[cptr];
			
				cptr++;
			}
			else if (code[cptr] == ']')
			{
				//lets find '['
				if (mem[mptr] != 0) 
					cptr = braket_right[cptr];
					
				cptr++;
			}
			else if (code[cptr] == '.')
			{
				//ignore output
				cptr++;
			}
			else if (code[cptr] == ',')
			{
				if (wptr < inputlen)
					mem[mptr] = inputdata[wptr++];
				else if (wptr == inputlen)
				{
					mem[mptr] = 255;
				}
				cptr++;
			}
			++runtime;
			if (runtime > 50000000) {
				mincptr = min(cptr, mincptr);
				maxcptr = max(cptr, maxcptr);
			}
		}

		if (cptr == codelen)
			printf("Terminates\n");

	}
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~