[BAEKJOON] 3954 Brainf**k 인터프리터 (Java)

[ 문제 ]

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 프로그램이 무한 루프에 빠지는지 안 빠지는지를 검사하기만 하면 된다. 따라서, 출력은 무시한다.

입력

첫째 줄에 테스트 케이스의 개수 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개 이하이다.

[ 핵심풀이 ]

0) 위에서 주어진조건대로 진행하면된다. 이해안갔던부분은

포인터와, 포인터가 가르키는 수에 대한 설명인데

Array를 조절할 수 있는 Index를 뜻하는 포인터.

Array[Index]란 값이 포인터가 가르키는 수 이다.

1) 대괄호 '[', ']' 에 대해서 Loop가 진행되므로, 각 위치에서 서로 Jump할 수 있도록 값을저장한 배열/리스트를 만든다

2) Loop가 5천만 이하거나, Index가 Code의 길이안에 존재할 경우 계속돌리고, 해당경우를 만족할 때 Code의 길이 끝까가면 Terminates, 아니라면 Loop가 해당되는 부분을 출력해주면된다.

3) Loop를 다시 찾기위해서 프로그램이 끝난 후 한번더 Loop만큼 돌려줄 때, 대괄호의 위치를 찾아낼 수 있다

[ 핵심소스 ]

int max=i,min=i;
while(loops-->0) {
	process();
	i++;
	max = Math.max(max, i);
	min = Math.min(min, i);
}
System.out.println("Loops "+(min-1)+" "+max);

[ Java ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class _3954_Brainfuck_인터프리터 {
    static int Memory, Code, Input;
    static String code, input;
	
    static int index, idx, loops, i;
    static int ary[];
    static int jump[];
    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int tc = Integer.parseInt(br.readLine());
        for(int t=1;t<=tc;t++) {
            st = new StringTokenizer(br.readLine());
            Memory = Integer.parseInt(st.nextToken());
            ary = new int[Memory];
            Code = Integer.parseInt(st.nextToken());
            jump = new int[Code];
            Input = Integer.parseInt(st.nextToken());
            code = br.readLine();
            input = br.readLine();
            Arrays.fill(jump, -1);
            find();
            solve();
        }
    }
    static void find() {
        Stack<Integer>s=new Stack<>();
        for(int i=0;i<code.length();i++) {
            if (code.charAt(i) == '[')
                s.push(i);
            else if (code.charAt(i) == ']') {
                int value = s.pop();
                jump[i] = value;
                jump[value] = i;
            }
        }
    }
    static void solve() {
        index=0;
        idx=0;
        loops=0;
        i=0;
        while(loops<=50000000 && i<Code) {
            process();
            i++;
            loops++;
        }
        if (loops <= 50000000)
            System.out.println("Terminates");
        else {
            int max=i,min=i;
            while(loops-->0) {
                process();
                i++;
                max = Math.max(max, i);
                min = Math.min(min, i);
            }
            System.out.println("Loops "+(min-1)+" "+max);
        }
    }
    static void process() {
        switch(code.charAt(i)) {
        case '+':
            ary[index] = (ary[index]+1)%256;
            break;
        case '-':
            ary[index] = (ary[index]-1+256)%256;
            break;
        case '<':
            index = index-1 >= 0 ? index-1:Memory-1;
            break;
        case '>':
            index = index+1 < Memory ? index+1:0;
            break;
        case '[':
            if (ary[index] == 0)
                i = jump[i];
            break;
        case ']':
            if (ary[index] != 0)
                i = jump[i];
            break;
        case '.':
            break;
        case ',':
            if (input.length() > idx)
                ary[index] = Integer.valueOf(input.charAt(idx++));
            else
                ary[index]=255;
            break;
        }
    }
	public static void main(String[] args) throws NumberFormatException, IOException {
        init();
    }
}