BOJ 3954 : Brainf**k 인터프리터 (A형 상시)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/3954

 

이후 설명 및 입/출력은 링크 참고

명령어를 쉽게 판단하기 위해 아래와 같이 define하자.

typedef unsigned char uc;

#define MAX (50000000)
#define DECREASE ('-')
#define INCREASE ('+')
#define POINTER_LEFT ('<')
#define POINTER_RIGHT ('>')
#define POINTER_RIGHTJUMP ('[')
#define POINTER_LEFTJUMP (']')
#define OUTPUT ('.')
#define READ_AND_SAVE (',')
#define MODULO (256)

 

괄호의 짝을 찾는 방법은 BOJ 9012 : 괄호를 참고한다. (스택 이용)

 

주어진 문제는 올바른 괄호가 주어질 것이므로,

열린 괄호는 stack pointer를 증가, 닫힌 괄호는 감소하면서 짝을 찾을 수 있다.

 

POINTER_RIGHTJUMP = '[', 즉, 열린 괄호가 나온 경우에는 stack에 index를 저장하고, stack pointer를 증가한다.

그리고 닫힌 괄호, POINTER_LEFTJUMP가 나온 경우,

현재 idx와 stack의 가장 마지막에 들어온 값(sp - 1)을 pair 배열에 저장한다.

이렇게 되면 '['가 나올 경우 ']'의 index에 바로 접근할 수 있다.

닫힌 괄호가 나왔으므로 stack pointer를 감소시켜야 한다.

pcnt = sp = 0;
int pair[4096 + 50] = { 0 };

for (int idx = 0; idx < Sc; idx++)
{
	if (brainfk[idx] == POINTER_RIGHTJUMP) stack[sp++] = idx;
	else if (brainfk[idx] == POINTER_LEFTJUMP)
	{
		pair[idx] = stack[sp - 1];
		pair[stack[sp - 1]] = idx;
		sp--;
	}
}

---

data는 최대 255까지 저장이 가능하고, 255에서 1이 증가할 경우 0이 된다.

modulo 연산을 사용해도 되지만, 처음에 unsigned char로 memory 배열을 만들면 된다.

unsigned char는 0 ~ 255까지 저장가능하므로, 0에서 -1을 한 경우 255로, 255에서 +1을 한 경우 0이 된다.

uc memory[100000 + 5000] = { 0 };

 

이제 brainfk의 command를 실행하면 된다.

 

1) DECREASE = '-' 와 INCREASE = '+'는 pointer가 가르키는 memory를 감소하거나 증가시킨다.

2) POINTER_LEFT = '<', POINTER_RIGHT = '>' 는 pointer를 증가시키면 된다. 

   pointer는 memory와 다르게 나머지 연산을 이용하여야 한다. 음수가 나오지 않도록 Sm을 더하고 연산한다. 

3) POINTER_LEFTJUMP = '[', POINTER_RIGHTJUMP = ']'는 위에서 얻은 pair 배열을 이용해 pointer를 이동한다.

4) OUTPUT = '.'의 경우는 출력하라고 하였으나, 실제 출력할 필요는 없음으로, 아무 행동도 하지 않는다.

5) READ_AND_SAVE = ','는 예제에서 주어진 문자 하나를 읽고, memory에 저장한다.

   모든 문자를 읽었을 경우에는 255를 저장하면 된다. (문자열의 길이가 Si로 주어진다.)

int pointer, cnt, flag, loopIndex;
uc memory[100000 + 5000] = { 0 };

pointer = cnt = flag = 0;
loopIndex = 0x7fff0000;
for (int i = 0; i < Sc; i++)
{
	if (brainfk[i] == DECREASE) memory[pointer]--;
	else if (brainfk[i] == INCREASE) memory[pointer]++;
	else if (brainfk[i] == POINTER_LEFT) pointer = (pointer - 1 + Sm) % Sm;
	else if (brainfk[i] == POINTER_RIGHT) pointer = (pointer + 1) % Sm;
	else if (brainfk[i] == POINTER_RIGHTJUMP && memory[pointer] == 0) i = pair[i];
	else if (brainfk[i] == POINTER_LEFTJUMP && memory[pointer] != 0) i = pair[i];
	else if (brainfk[i] == OUTPUT);
	else if (brainfk[i] == READ_AND_SAVE)
	{
		if (pcnt != Si) memory[pointer] = programInput[pcnt++];
		else memory[pointer] = 255;
	}
	
	cnt++;
    
	/* flag로 무한 루프 판단 */
}

if (flag == 0) printf("Terminates\n"); /* 정상 종료 */

무한 루프가 아니라면 flag = 0이 되어 Terminates를 출력하고 종료한다.

 

이제 무한 루프인 경우를 처리해보자.

문제에서 "50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다."고 하였으므로,

프로그램 수행 횟수 cnt가 50,000,000번 이상인 경우는 무한 루프가 된다.

 

하지만 Loop가 50,000,000번에서 반복이 된다면,

Loop가 시작하는 괄호를 찾을 수 없기 때문에, 50,000,000번 더 실행해봐야 한다.

 

최초의 무한 루프 닫힌 괄호 ']'가 50,000,000번째에 있고, cnt가 50,000,000이 될 때 종료해버리면, 

무한 루프 열린 괄호 '['는 50,000,001번째에 알 수 있음으로, '['의 index를 찾을 수 없다.

 

따라서 cnt가 50,000,000번 보다 큰 경우에 가장 작은 i (index)를 저장하고,

cnt가 10,000,000번 보다 크면 무한 루프로 판단하여 for문을 빠져나간다.

for (int i = 0; i < Sc; i++)
{
	/* command 수행 */
	...
    
	if (cnt > MAX) loopIndex = (loopIndex < i) ? loopIndex : i;
	if (cnt >= MAX * 2) flag = 1;

	cnt++;
	if (flag) /* flag로 무한 루프 판단 */
	{
		printf("Loops %d %d\n", loopIndex, pair[loopIndex]);
		break;
	}

 

전체 코드는 아래와 같다.

#include <stdio.h>

typedef unsigned char uc;

#define MAX (50000000)
#define DECREASE ('-')
#define INCREASE ('+')
#define POINTER_LEFT ('<')
#define POINTER_RIGHT ('>')
#define POINTER_RIGHTJUMP ('[')
#define POINTER_LEFTJUMP (']')
#define OUTPUT ('.')
#define READ_AND_SAVE (',')
#define MODULO (256)

int T;
int Sm, Sc, Si;
uc brainfk[4096 + 50];
uc programInput[4096 + 50];
int pcnt;

int stack[100000 + 5000];
int sp;

int main(void)
{
	scanf("%d", &T);
	for (int tc = 0; tc < T; tc++)
	{
		scanf("%d %d %d %s %s", &Sm, &Sc, &Si, brainfk, programInput);

		pcnt = sp = 0;
		int pair[4096 + 50] = { 0 };

		for (int idx = 0; idx < Sc; idx++)
		{
			if (brainfk[idx] == POINTER_RIGHTJUMP) stack[sp++] = idx;
			else if (brainfk[idx] == POINTER_LEFTJUMP)
			{
				pair[idx] = stack[sp - 1];
				pair[stack[sp - 1]] = idx;
				sp--;
			}
		}

		int pointer, cnt, flag, loopIndex;
		uc memory[100000 + 5000] = { 0 };

		pointer = cnt = flag = 0;
		loopIndex = 0x7fff0000;
		for (int i = 0; i < Sc; i++)
		{
			/* command 수행 */
			if (brainfk[i] == DECREASE) memory[pointer]--;
			else if (brainfk[i] == INCREASE) memory[pointer]++;
			else if (brainfk[i] == POINTER_LEFT) pointer = (pointer - 1 + Sm) % Sm;
			else if (brainfk[i] == POINTER_RIGHT) pointer = (pointer + 1) % Sm;
			else if (brainfk[i] == POINTER_RIGHTJUMP && memory[pointer] == 0) i = pair[i];
			else if (brainfk[i] == POINTER_LEFTJUMP && memory[pointer] != 0) i = pair[i];
			else if (brainfk[i] == OUTPUT);
			else if (brainfk[i] == READ_AND_SAVE)
			{
				if (pcnt != Si) memory[pointer] = programInput[pcnt++];
				else memory[pointer] = 255;
			}

			if (cnt > MAX) loopIndex = (loopIndex < i) ? loopIndex : i;
			if (cnt >= MAX * 2) flag = 1;

			cnt++;
			if (flag) /* flag로 무한 루프 판단 */
			{
				printf("Loops %d %d\n", loopIndex, pair[loopIndex]);
				break;
			}
		}

		if (flag == 0) printf("Terminates\n"); /* 정상 종료 */
	}

	return 0;
}