문제링크
문제
Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오.
무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다.
Brainf**k 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다. Brainf**k 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다.
- | 포인터가 가리키는 수를 1 감소시킨다. (modulo 28) |
|---|---|
+ | 포인터가 가리키는 수를 1 증가시킨다. (modulo 28) |
< | 포인터를 왼쪽으로 한 칸 움직인다. |
> | 포인터를 오른쪽으로 한 칸 움직인다. |
[ | 만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다. |
] | 만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다. |
| . | 포인터가 가리키는 수를 출력한다. |
| , | 문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다. |
인터프리터는 Brainf**k 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. 물론 [이나 ]인 경우에는 다음 명령으로 이동하는 것이 아니라 점프를 한다.
데이터 배열의 크기는 문제에서 주어지는 값을 사용해야 한다. 또, 데이터 배열의 값이 underflow나 overflow를 일으켰을 때는 일반적인 방법을 따르면 된다. 프로그램을 수행하기 전에, 데이터 배열의 값은 0으로 초기화되어 있고, 포인터가 가리키는 칸은 0번 칸이다.
포인터를 왼쪽이나 오른쪽으로 움직일 때, 데이터 배열의 범위를 넘어간다면, 반대쪽으로 넘어가게 된다. 즉, 포인터가 0을 가리킬 때, 1을 감소시킨다면, 배열의 크기 - 1번째를 가리키게 된다.
[와 ]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서 [의 개수에서 ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.
이 문제는 Brainf**k 프로그램이 무한 루프에 빠지는지 안 빠지는지를 검사하기만 하면 된다. 따라서, 출력은 무시한다.
풀이 유형
풀이
복잡하게 생각할 것 없이 구현 문제다. 다만, 테스트 케이스가 여러 개 인풋으로 주어지는 만큼, 전역 변수의 초기화는 잊지 말도록 하자. 구현에 있어서 단순히 생각하면, 안 되는 것들이 몇 가지 있다.
- 대괄호 각 짝의 위치를 미리 저장해야 한다. ( 그때 그떄 찾아서는 시간초과가 난다. )
- 무한 루프를 제대로 판별하자.
1. 대괄호의 짝
내 코드에서는 hash를 사용했지만, 그냥 배열을 사용해도 된다. 어차피 명령어의 길이가 충분히 짧기 때문이다. 만약 여는 대괄호 ‘[‘가 커맨드의 n번째(이하 cmd[n])라고 할 때 우리는 배열에 해당 여는 대괄호의 짝꿍인 닫는 대괄호 ‘]’를 미리 메모이제이션하자.
예를 들어,
1
[++]
위와 같은 인풋이 있다고 하자, 그러면 괄호의 짝꿍의 위치를 저장하는 배열 dic에 대하여, dic[0] = 3, dic[3] = 0이 될 것이다.
2. 무한 루프 판별
작년 즈음에 추가 된 데이터로 엄청나게 많은 수의 코드가 AC를 받지 못하게 된 원흉이다. 무한 루프의 정의에 대해서 먼저 생각을 해야 하는데, 만약
1
++[[++]+]
위와 같은 명령어가 들어온다고 생각해보자. 우리는 nested loop를 마주하게 된다. “Loops 2, 8” 안에 “Loops 3,6”이 있다. 이를 실행해보면 알겠지만, “Loops 3,6”에 들어서는 순간 pointer가 향하는 값이 홀수일 경우, 영원히 빠져나오지 못한다.(즉, 무한루프에 걸린다.) 이때 내가 예전에 작성했던 코드에서는 제일 바깥의 루프, 즉 “Loops 2, 8”을 단순히 max연산을 통해 구했는데, ‘무한 루프’의 정의가 좀 더 명확히 세워지면서 잘못된 접근 방식이 되었다.
본론만 말하자면, 한 번 더 5000만 번 실행해보면 된다. 프로그램 카운터를 그대로 유지한 채로 다시 한 번 5000만 번의 루프를 실행하는 것이다. 한 번 더 실행하면서, 어디서부터 어디까지가 범위인지를 파악해주면 그것이 무한루프의 위치인 것이다.
start = min(start, pc);
end = max(end, pc);
코드의 이 부분은 루프를 판별하기 위해 넣은 것인데, 사실 start를 업데이트 해 줄 필요도 없다. 왜냐하면 우리는 위에서 대괄호의 짝을 이미 찾아놨기 때문에, 그냥 dic에서 해당 값을 뽑아 쓰면 되는 것이다.
마무리
무한 루프의 판별, 그것도 위치의 판별이란 것에 접근하기가 어렵다. 사실 단순히 MAX값 만큼 다시 명령어를 실행시키는 것은 그리 효율적이지 않다. 조금 더 좋은 풀이가 있을 지도 모르겠지만, 내 머리로는 생각이 나지 않는다. 더군다나, 이런 풀이 방법으로 느리다는 천형을 가진 파이썬이 과연 AC를 받을 수 있을지는 모르겠다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#define Min(X, Y) ((X) < (Y) ? (X) : (Y))
#define Max(X, Y) ((X) > (Y) ? (X) : (Y))
#define MAX 100000
#define INF 2100000000
using namespace std;
char cmd[4097];
int loop;
int input[4097];
int arr[100000];
int main(void){
ios::sync_with_stdio(false); cin.tie(NULL);
int T; cin>>T;
for(int tc=0;tc<T;tc++){
map<int, int> dic;
stack<int> stk;
memset(arr,0,sizeof(arr));
loop = 0;
int pointer = 0;
int charpointer = 0;
int pc = 0;
int r = 0;
bool flag = true;
int M,C,I; cin>>M>>C>>I;
for(int i=0; i<C; i++){
cin>>cmd[i];
}
for(int i=0; i<I; i++){
char c;
cin>>c;
input[i] = c;
}
for(int i=0; i<C; i++){
if(cmd[i] == '[') stk.push(i);
else if(cmd[i] == ']'){
int a = stk.top();
stk.pop();
dic[a] = i;
dic[i] = a;
}
}
for(int l=0; l<2; l++){
int start = C+1, end = 0;
loop = 0;
while(pc < C){
start = min(start, pc);
end = max(end, pc);
char c = cmd[pc];
loop += 1;
switch(c){
case '-' :
arr[pointer] -= 1;
if(arr[pointer] < 0) arr[pointer] += 256;
break;
case '+' :
arr[pointer] += 1;
if(arr[pointer] >= 256) arr[pointer] -= 256;
break;
case '<' :
pointer -= 1;
if(pointer < 0) pointer += C;
break;
case '>' :
pointer += 1;
if(pointer >= C) pointer -= C;
break;
case '[' :
if(arr[pointer] == 0){
pc = dic[pc];
}
break;
case ']' :
if(arr[pointer] != 0){
r = max(r, pc);
pc = dic[pc];
}
break;
case '.' :
break;
case ',' :
if(charpointer < I) arr[pointer] = input[charpointer];
else arr[pointer] = 255;
charpointer++;
break;
}
pc += 1;
if(loop > 50000000){
flag = false;
break;
}
}
if(flag){
cout<<"Terminates"<<endl;
break;
}
else if(!flag && l == 1){
cout<<"Loops "<<dic[end]<<" "<<end<<endl;
}
}
}
}