[ 백준 3954 ] Brainf**k 인터프리터 ( 자바 )

[ 백준 3954 ] Brainf**k 인터프리터 ( java ) 

 

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

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

 

 

 

인터프리터는 Brainfuck 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. ([와 ]인 경우에는 점프를 할 수 있다.)

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

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

[와 ]는 루프를 의미하며, 중첩될 수 있다. 잘 짜여진 프로그램은 프로그램을 수행하면서, 각 명령을 수행하기 전까지 나온 [ 개수에서 ] 개수를 빼면 0보다 크거나 같은 값이 나오게 된다. 프로그램이 종료된 후에는 0이 나온다.

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

 

 

 

출처: 백준, https://www.acmicpc.net/problem/3954

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

 

 

핵심 

1 unsigned 8bit 정수 

1<<8 modulo 처리하기 

 

2 stack 사용

 코드에서 [, ] 쌍끼리 점프해야하기 때문에, 코드 명령을 실행하기에 앞서 [, ] 쌍의 서로의 위치를 pairs에 저장했다. pairs에 저장하기 위해 맞는 쌍의 [ ] 를 찾아야 하므로 stack 사용해야 한다. 

 

3 Loop 찾기 

실행은 최대 50000000번만 실행된다. " 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다."

 

 3-1 언제 종료될까? 

종료는 code 인덱스가 code길이와 같으면 종료된다. 

 

 3-2 무한 루프 위치를 어떻게 찾을까?

가장 바깥쪽 루프 찾기 = 가장 큰 ]의 인덱스 찾기 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

 

코드

 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int TC = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        int[] arr = new int[100001];
        int arrLen ;
        int ptr;
        
        char[] codes = new char[4097];
        int codeLen ;
        int code_i;
        
        char[] input = new char[4097];
        int inputLen ;
        int input_i;
        int div = 1 << 8;
        for(int tc = 0 ; tc < TC ; tc++) {
            st = new StringTokenizer(br.readLine());
            arrLen = Integer.parseInt(st.nextToken());
            codeLen = Integer.parseInt(st.nextToken());
            inputLen = Integer.parseInt(st.nextToken());
            
            for(int i = 0 ; i < arrLen ; i++) {
                arr[i] = 0;
            }
            String tmp = br.readLine();
            for(int i = 0 ; i < codeLen ; i++) {
                codes[i] = tmp.charAt(i);
                pairs[i] = -1;
            }
            
            tmp = br.readLine();
            for(int i = 0 ; i < inputLen ; i++) {
                input[i] = tmp.charAt(i);
            }
            
            
            ptr = 0;
            code_i = 0;
            input_i = 0;
            
            // pairs에 맞는 [ ] 쌍 위치 저장 
            makePair(codes, codeLen);
            
            int cmd;
            int lastLoop = -1;
            for(cmd = 0 ; cmd < 50000000 ; cmd++) {
                if(codes[code_i] == '+') {
                    arr[ptr]++;
                    arr[ptr] = arr[ptr] % div;
                    code_i++;
                }else if(codes[code_i] == '-') {
                    arr[ptr]--;
                    if(arr[ptr] < 0)
                        arr[ptr] = div - 1;
                    code_i++;
                }else if(codes[code_i] == '<') {
                    ptr--;
                    if(ptr < 0)
                        ptr = arrLen - 1;
                    code_i++;
                }else if(codes[code_i] == '>') {
                    ptr++;
                    if(ptr == arrLen)
                        ptr = 0;
                    code_i++;
                }else if(codes[code_i] == '[') {
                    if(arr[ptr] == 0) {
                        code_i = pairs[code_i];
                    }else {
                        code_i++;
                    }
                }else if(codes[code_i] == ']') {
                    if(arr[ptr] != 0) {
                        if(lastLoop < code_i)
                            lastLoop = code_i;
                        code_i = pairs[code_i];
                    }else {
                        code_i++;
                    }
                }else if(codes[code_i] == '.') {
                    code_i++;
                }else {
                    if(input_i == inputLen) {
                        arr[ptr] = 255;
                    }else {
                        arr[ptr] =  input[input_i++];
                    }
                    code_i++;
                }
                
                if(code_i == codeLen)
                    break;
            }
            if(code_i == codeLen)
                System.out.println("Terminates");
            else
                System.out.println("Loops " +pairs[lastLoop]+" "+lastLoop);
        }
    }
    static int[] pairs = new int[4097];
    static void makePair(char[] codes, int codeLen ) {
        Stack<Integer> stack = new Stack<Integer>();
        int closePair ;
        
        for(int i = 0 ; i < codeLen ; i++) {
            if(codes[i] == '[') {
                stack.push(i);
            }
            if(codes[i] == ']') {
                closePair = stack.pop();
                pairs[i] = closePair;
                pairs[closePair] = i;
            }
        }
    }
}