[ 백준 - 3954번 / 구현 ] Brainf**k 인터프리터 (삼성기출)

1. 문제

---

 

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

문제

Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오.

Brainf**k 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다. Brainf**k 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다.

-+<>[].,

포인터가 가리키는 수를 1 감소시킨다. (modulo 28)

포인터가 가리키는 수를 1 증가시킨다. (modulo 28)

포인터를 왼쪽으로 움직인다.(1 감소)

포인터를 오른쪽으로 움직인다.(1 증가)

만약 포인터가 가리키는 수가 0과 같다면, [와 짝을 이루는 ]로 점프한다.

만약 포인터가 가리키는 수가 0이 아니라면, ]와 짝을 이루는 [로 점프한다.

포인터가 가리키는 수를 출력한다.

문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.

인터프리터는 Brainf**k 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. 물론 [이나 ]인 경우에는 다음 명령으로 이동하는 것이 아니라 점프를 한다.

데이터 배열의 크기는 문제에서 주어지는 값을 사용해야 한다. 또, 데이터 배열의 값이 underflow나 overflow를 일으켰을 때는 일반적인 방법을 따르면 된다. 프로그램을 수행하기 전에, 데이터 배열의 값은 0으로 초기화되어 있고, 포인터가 가리키는 칸은 0번 칸이다.

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

[와 ]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서 [의 개수에서 ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.

이 문제는 Brainf**k 프로그램이 무한 루프에 빠지는지 안 빠지는지를 검사하기만 하면 된다. 따라서, 출력은 무시한다.

입력

첫째 줄에 테스트 케이스의 개수 t (0 < t ≤ 20)가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 sm, sc, si가 주어진다. sm은 메모리(배열)의 크기이고, sc는 프로그램 코드의 크기, si는 입력의 크기이다. (0 < sm ≤ 100,000, 0 < sc, si < 4096)

둘째 줄에는 Brainf**k 프로그램이 주어진다. 프로그램은 sc개의 문자로 이루어져 있다.

셋째 줄에는 프로그램의 입력이 주어진다. (공백이 아니면서 출력할 수 있는 문자만 주어진다)

출력

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([와 ]의 위치) 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

예제 입력 1 복사

4 10 4 3 +-., qwe 1000 5 1 +[+-] a 100 74 4 +++++[->++<]>[-<+++++++>]<[->+>+>+>+<<<<]>+++>--->++++++++++>---<<<.>.>.>. xxyz 9999 52 14 +++++[>+++++++++<-],+[-[>--.++>+<<-]>+.->[<.>-]<<,+] this_is_a_test

예제 출력 1 복사

Terminates Loops 1 4 Terminates Terminates

 

 

 

 

2. 소스코드

---

1회차

 

- 루프 pair를 찾고, 무한 루프를 판별하는게 전부인 문제. 나머지는 그냥 문제에 적힌대로 구현하면 된다.

- 무한 루프를 판별하는 것이 모호했음.

- 무한 루프를 판별하기 위해, 루프에 진입시 true 탈출시 false 를 저장하는 배열 2개를 이용함. ( loopIn, loopOut)

- 명령어 oper의 인덱스 최대 값을 이용해 무한 루프를 판별하는 코드도 존재함. 이 방법은 배열을 쓸 필요도 없고 변수하나만 사용하면 되서 효율적임. 근데 한번 순회하고 무한 루프에 빠지는 경우가 반례가됨. 이러한 코드는 생길 수 가 없는 건지, 정답 체크 data에 없는 건지 무튼 정답 처리됨. 잘 모르겠음.

 

 

#include <iostream>
#include <cstring>
using namespace std;
#define MAXSIZE 4097
#define MAXRUN 50000000
struct TcInfo
{
	int arrSize, codeSize, inSize;
	string oper, input;
};

int arr[100000], pairList[MAXSIZE], loopIn[MAXSIZE],loopOut[MAXSIZE];
 
void findPair(TcInfo info) {
	for (int i = 0; i < info.codeSize; ++i) {
		if (info.oper[i] == '[') {
			int openCnt = 0;
			for (int j = i + 1; j < info.codeSize; ++j) {
				if (info.oper[j] == '[') ++openCnt;
				if (info.oper[j] == ']') {
					if (openCnt == 0) {
						pairList[i] = j;
						pairList[j] = i;
						break;
					}
					openCnt--;
				}
			}
		}
	}
}

void isLoopProgram(TcInfo info) {
	int runCnt = 0;
	int ptr = 0;
	int inputIdx = 0;
 
	for (int operIdx = 0; operIdx < info.codeSize; ++operIdx) {
		if (runCnt > MAXRUN) {
			int infiLoop;
			for (int i = 0; i < info.codeSize; ++i) {
				if (info.oper[i] == '[') {
					if (loopIn[i] == true and loopOut[pairList[i]] == false) {
						infiLoop = i;
					}
				}
			}
			cout << "Loops " << infiLoop << " " << pairList[infiLoop] << '\n';
			return;
		}

		char cmd = info.oper[operIdx];
		switch (cmd)
		{
		case '<'://포인터를 왼쪽으로 움직인다.(1 감소)
			ptr = ptr - 1 < 0 ? info.arrSize - 1 : ptr - 1;
			break;

		case '>'://	포인터를 오른쪽으로 움직인다.(1 증가)
			ptr = ptr + 1 > info.arrSize - 1 ? 0 : ptr + 1;
			break;
		case '-': //포인터가 가리키는 수를 1 감소시킨다. (modulo 28)
			arr[ptr] = arr[ptr] - 1 < 0 ? 255 : arr[ptr] - 1;
			break;
		case '+'://포인터가 가리키는 수를 1 증가시킨다. (modulo 28)
			arr[ptr] = arr[ptr] + 1 > 255 ? 0 : arr[ptr] + 1;
			break;
		case ',': //문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.
			arr[ptr] = inputIdx >= info.inSize ? 255 : (int)info.input[inputIdx];
			inputIdx = inputIdx >= info.inSize ? inputIdx : inputIdx + 1;
			break;
		case '['://	만약 포인터가 가리키는 수가 0과 같다면, [와 짝을 이루는 ]로 점프한다.
			if (arr[ptr] == 0) { //점프 : 루프를 들어간 것이 아님.
				operIdx = pairList[operIdx];
				loopIn[operIdx] = false;
			}
			else { 
				// 패스 : 루프를 들어갔음.
				loopIn[operIdx] = true; 
			}
			break;
		case ']'://	만약 포인터가 가리키는 수가 0이 아니라면, ]와 짝을 이루는 [로 점프한다.
			if (arr[ptr] != 0) {
				//점프 : 루프를 나온것이 아님.
				operIdx = pairList[operIdx];
				loopOut[operIdx] = false;
			}
			else { 
				// 패스 : 루프를 나왔음.
				loopOut[operIdx] = true;
			}
			break;
		}
		++runCnt;
	}//end for : operIdx 문 
	cout << "Terminates" << '\n';
	return;
}

void brainFuck(int tc) {
	while (tc--)
	{
		TcInfo info;
		cin >> info.arrSize >> info.codeSize >> info.inSize >> info.oper >> info.input;
		findPair(info);
		isLoopProgram(info);	
		memset(arr, 0, sizeof(arr));
		memset(pairList, 0, sizeof(pairList));
		memset(pairList, 0, sizeof(loopIn));
		memset(pairList, 0, sizeof(loopOut));
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int tc; cin >> tc;
	brainFuck(tc);
	return 0;
}