[알고리즘 문제 풀이][시뮬레이션] 백준 3954번 - Brainf**k 인터프리터

백준 3954번 Brainf**k 인터프리터 문제입니다.

(GCPC 2012년도 B번 문제 / 삼성 A형 기출 복원문제)

 

- 문제 설명: https://www.acmicpc.net/problem/3954

- 문제 풀이:

 

본 문제는 Brainf**k 언어로 구성된 문장과 인풋이 들어오면 그것을 해석하는 인터프리터를 구현하는 문제입니다. 복잡한 알고리즘이 아닌 스택 & 구현 능력이 필요한 문제였습니다. 다만 문제에서 해석이 어려운 부분은 이 문제에서 정의하는 "무한루프" 가 무엇인가인데, 본 문제의 질문검색 게시판의 토론 결과를 보면 특정 시점부터 탈출하지 않는 가장 안쪽 루프가 됩니다.

 

[[]] 이런 식으로 루프가 중첩된 경우, 가장 바깥쪽 루프는 안쪽 루프에 갇혀 영원히 탈출할 수 없지만, 정확한 무한루프는 안쪽 루프가 해당합니다. 다만 문제에서 무한 루프 안에서는 50,000,000 개의 명령어만 실행한다는 제한을 주었기 때문에 본 문제를 단순 구현 + 50,000,000 범위 안에 갇힌 위치 알아내기로 구현하면 됩니다. 무한 루프 위치 찾기는 스포일러가 될 수 있기 때문에 문제를 풀어본 후에 제 답변 혹은 다른 분들의 답변을 보시는 것을 추천합니다.

 

본 문제를 풀면서 개인적으로 고려한 점들은 다음과 같습니다.

1. 문제에서 구현해야 하는 내용들이 많기 때문에 최대한 함수를 기능별로 쪼개서 디버깅하기 쉽게 나눌 것

2. 루프 내 점프를 쉽게 하기 위하여, 먼저 루프 쌍들의 서로 위치를 저장 (아래 코드의 jumps[] 배열)

3. 코드 실행시 스택 자료구조에 현재 진행 중인 루프 (답 출력을 위해) 와 누적 명령어 실행 횟수 (갇힌 루프 위치 알아내기 위해)를 저장

 

무한 루프의 위치를 찾는 것은 충분히 많이 (5천만 * 2배) 명령어를 실행하여 무한 루프에 빠지게 한 후에, 5천만 개의 명령어 실행 횟수 내에 들어온 가장 바깥쪽 루프를 선택하였습니다. 이 범위를 넘어가면 문제에서 정한 무한 루프가 아니게 되고, 이 범위 안에 들어온 가장 바깥쪽 첫번째 루프가 무한 루프가 됩니다. 그 안에 들어있는 중첩된 루프들은 무한히 도는 것이 아니라 언젠가 탈출했기 때문에 그 바깥 루프가 5천만 횟수 안에 들어오는 것이 됩니다.

 

①[ 아직 무한 루프 아님 ②[ 뭔가 실행 ③[ 뭔가 실행2  ]  뭔가 실행 3] 무한 루프 때문에 여기로 다시 못 나옴 ]

 

이런 형태의 루프가 진행이 된다면 ② 이 무한루프 일때, ② 는 5천만 번 안에 다시 방문하게 되고, ③은 당연히 5천만 횟수 안에는 탈출하게 됩니다. ① 은 5천만 번 보다도 훨씬 더 전에 진입했고 다시는 방문하지 못하기 때문에 지금 누적 실행 횟수와는 점점 더 격차가 벌어지게 됩니다. 따라서 지금 루프 실행 스택 상태인 (왼쪽부터 차곡차곡 쌓여 들어갑니다) ①-②-③ 중에 5천만 누적 횟수 안에 들어온 가장 첫번째는 ② 가 됩니다.

 

- 코드:

실제 코드는 다음과 같습니다. (2021.08.23)

 

#include <stdio.h>

int msize;
int csize;
int isize;
int pointer;
int input_index;

unsigned char codes[4096];
unsigned char inputs[4096];
unsigned char memory[100010];
int jumps[4096]; 

int stack[5000];
int stack_pos[5000];
int cptr;
int sp;
int tc;

void preprocess(void)
{
	sp = 0;
	for (int i = 0; i < csize; i++) {
		if (codes[i] == '[') {
			sp++;
			stack[sp] = i;
		}
		if (codes[i] == ']') {
			jumps[stack[sp]] = i;
			jumps[i] = stack[sp];
			sp--;
		}
	}
}

int do_code(int index)
{
	int ret = index + 1;

	if (codes[index] == '-') {
		memory[pointer] = (memory[pointer] + 256 - 1) % 256;
	}
	else if (codes[index] == '+') {
		memory[pointer] = (memory[pointer] + 1) % 256;
	}
	else if (codes[index] == '<') {
		pointer = (pointer + msize - 1) % msize;
	}
	else if (codes[index] == '>') {
		pointer = (pointer + 1) % msize;
	}
	else if (codes[index] == '[') {
		if (memory[pointer] == 0) { /* loop pass */
			ret = jumps[index] + 1;
		}
		else {
			stack_pos[sp] = cptr;
			stack[sp] = index;
			sp++;
		}
	}
	else if (codes[index] == ']') {
		if (memory[pointer] != 0) {
			ret = jumps[index] + 1;
			stack_pos[sp - 1] = cptr; /* update */
		}
		else sp--; /* loop end */
	}
	else if (codes[index] == ',') {
		if (input_index >= isize) {
			memory[pointer] = 255;
		}
		else {
			memory[pointer] = inputs[input_index++];
		}
	} // pass "."

	return ret;
}

void run(void)
{
	int max_code = 50000001;
	int index = 0;
	int i;

	pointer = 0;
	input_index = 0;
	sp = 0;
	cptr = 0;

	/* terminates within 50 000 000 instructions */
	while (max_code--) {
		if (index >= csize) {
			printf("Terminates\n");
			return;
		}
		index = do_code(index);
		cptr++;
	}

	/* at most 50 000 000 instructions within infinite loop */
	max_code = 50000001;
	while (max_code--) {
		index = do_code(index);
		cptr++;
	}

	for (i = 0; i < sp; i++) {
		if (cptr-1-stack_pos[i] <= 50000000) {
			printf("Loops %d %d\n", stack[i], jumps[stack[i]]);
			break;
		}
	}
}

void init(void)
{
	scanf("%d %d %d", &msize, &csize, &isize);

	for (int i = 0; i < msize; i++) {
		memory[i] = 0;
	}
	for (int i = 0; i < csize; i++) {
		scanf(" %c", &codes[i]);
	}
	getchar();
	for (int i = 0; i < isize; i++) {
		scanf(" %c", &inputs[i]);
	}
	getchar();
}

int main(void)
{
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {

		/* get input & init arrays */
		init();

		/* [[ ]] find sets */
		preprocess();

		/* start codes */
		run();
	}
}

 

- 실수 포인트 & 반례:

본 문제를 풀면서 실수한 내용들은 다음과 같습니다.

(1) character 자료형 input 받을 때의 실수

char 을 받기 때문에 단순히 for문을 돌면서 %c로 받도록 하였으나, 이런 경우 엔터키에 해당하는 개행문자 (\n) 까지도 입력이 되기 때문에 char 배열 안에 엔터까지도 입력이 되어버렸습니다. 이를 해결하기 위해 찾아본 결과 fflush(stdin); 은 맞지 않는 방법이라고 하여, getchar(); 를 써서 개행 문자가 따로 받아지도록 처리하였습니다.

 

(2) 문제 답안 중 Terminates 출력 조건 실수

Terminates 출력을 5천만번 실행 안에 하도록 했는데, 본 코드의 while문의 경우 정확히 5천만번째에 코드 실행이 끝나면 Loops 로 처리하게 되어있었습니다. 해당 edge case에 걸리지 않도록 루프를 5천만 1번 돌렸습니다.

- 반례: https://www.acmicpc.net/board/view/61124

Input :
2
65359 16 3
+[>+],...[[-],+]
999
65359 16 3
+[>+],[[-],+]+[]
999

Answer :
Terminates
Loops 14 15

 

(3) 무한 루프 기준을 가장 최근 진입한 루프로 잘못 설정

무한 루프에 빠지면 탈출하지 못한다는 개념만 생각하고 가장 마지막 진입한 루프로 잘못 풀었습니다. 그러나 무한 루프 안에서도 탈출하는 여러 루프들이 있을 수 있습니다. (while(True) 안에 있는 다양한 for문들을 생각해보면...)

- 반례: https://www.acmicpc.net/board/view/61103

Input
2
3 124 1
+[-[[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+]----------------------------------[+]]++]
.
1 8 1
+[-[]++]
.

Output
Loops 1 123
Loops 3 4

 

(4)  명령어를 너무 적게 실행하여 무한 루프에 갇히지 않음

정확히 5천만번째에 무한 루프에 진입한다면, Terminates 여부를 알기 위해 명령어를 5천만번만 진행한다면 무한루프에 제대로 갇히지 않을 수 있습니다.

- 반례: https://www.acmicpc.net/board/view/61124

Input
1
3 209 1
+[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+],[-].+[-[[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+]----------------------------------[+]]++]
1

Output
Loops 86 208

 

(5) 무한 루프 기준을 메모리 값의 변화를 기준으로 설정한 것

일반적인 while 루프 탈출 기준을 생각해봤을 때, 기준이 되는 변수값이 변화하지 않으면 탈출하지 않는다고 생각해서 다시 그 루프로 돌아왔을 때 메모리가 변하지 않으면 무한 루프라고 판정하도록 코드를 변경하였습니다. 그러나 Brain f**k 문법의 경우, 메모리가 0이 아니면 루프 진입이기 때문에 ++ 로 무한히 늘리면 메모리는 변경되면서 무한히 돌게 됩니다.

- 반례: https://www.acmicpc.net/board/view/58310

===== 입력 =====
2
10 5 1
+[[]]
a
1 9 1
++[[++]+]
a

===== 출력 =====
Loops 2 3
Loops 3 6

 

(6) 5번의 문제를 해결하고자 메모리 변경이 없는 경우, 가장 안쪽 루프를 무한 루프로 판정

메모리가 변경되지 않으면 무한 루프로 생각하고, 혹시 5번의 반례처럼 메모리가 변경되어 무한루프를 찾지 못하면 가장 안쪽 루프를 무한루프로 판정하게 하였습니다. 그러나 무조건 가장 안쪽 루프가 무한 루프라는 보장이 없었습니다. 이런 반례가 없었기 때문에 직접 만들어서 테스트해보았습니다. 아래의 코드는 1억번째에 우연히 무한 루프 안의 중첩 루프에 걸려있게 됩니다.

- 반례:

Input:
1
8 23 1
++[[[>>>>>>]<<<<<<++]+]
a

Output:
Loops 3 20

 

(7) 자료형 지정 오류

제일 근본적인 오류가 있었으며, 그걸 가장 마지막에 발견하는 치명적인 실수가 있었습니다... 루프 쌍 간 서로의 인덱스를 저장하는 jumps[] 배열을 만들었는데, 이 안에는 0~4096 만큼 코드 범위를 저장할 수 있어야하는데 unsigned char 자료형으로 지정해버렸고, 그래서 채점 데이터로는 당연히 틀리게 되었습니다. (문제의 샘플 케이스나 반례는 길이가 짧았기 때문에 검출되지 않았습니다.) 이런 경우를 잡기 위해서는 랜덤 답안 생성 코드도 만드는 것이 좋을 것 같습니다.