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

https://www.acmicpc.net/problem/3954

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

---

문제

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

무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다.

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

-	포인터가 가리키는 수를 1 감소시킨다. (modulo $2^8$)
+	포인터가 가리키는 수를 1 증가시킨다. (modulo $2^8$)
<	포인터를 왼쪽으로 한 칸 움직인다.
>	포인터를 오른쪽으로 한 칸 움직인다.
[	만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다.
]	만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다.
.	포인터가 가리키는 수를 출력한다.
,	문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.

인터프리터는 Brainf**k 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. 물론 [이나 ]인 경우에는 다음 명령으로 이동하는 것이 아니라 점프를 한다.

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

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

[와 ]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서 [의 개수에서 ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.

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

입력

첫째 줄에 테스트 케이스의 개수 t (0 < t ≤ 20)가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 $s_m$, $s_c$, $s_i$가 주어진다. $s_m$은 메모리(배열)의 크기이고, $s_c$는 프로그램 코드의 크기, $s_i$는 입력의 크기이다. (0 < $s_m$ ≤ 100,000, 0 < $s_c$, $s_i$ < 4096)

둘째 줄에는 Brainf**k 프로그램이 주어진다. 프로그램은 $s_c$개의 문자로 이루어져 있다.

셋째 줄에는 프로그램의 입력이 주어진다. (공백이 아니면서 출력할 수 있는 문자만 주어진다)

출력

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([와 ]의 위치) 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

728x90

 

예제 입력 1

4
10 4 3
+-.,
qwe
1000 5 1
+[+-]
a
100 74 4
+++++[->++<]>[-<+++++++>]<[->+>+>+>+<<<<]>+++>--->++++++++++>---<<<.>.>.>.
xxyz
9999 52 14
+++++[>+++++++++<-],+[-[>--.++>+<<-]>+.->[<.>-]<<,+]
this_is_a_test

예제 출력 1

Terminates
Loops 1 4
Terminates
Terminates

---

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

public class Main {
	
	static int sm; // 메모리 배열 크기
	static int si; // 입력의 크기
	
	static int[] arr; // 배열
	static char[] code;  // 명령
	static char[] input;  // 입력
	static int[] bracket; // 각 괄호의 짝 인덱스
	
	static int p; // 포인터
	static int codeIdx; // 실행할 명령 인덱스
	static int inputIdx; // 다음 입력 인덱스
	
	private static void command() { // 명령을 수행하는 메소드
		switch (code[codeIdx]) {
		
		/*
		 * modulo 2^8이기 때문에
		 * 255에서 1을 더하면 256이 아니라 0이 되고
		 * 0에서 1을 빼면 -1이 아니라 255가 된다
		 */
		
		case '-': { // 포인터가 가리키는 수를 1 감소시킨다.
			arr[p] = arr[p] == 0 ? 255 : arr[p] - 1;
			break;
		}
		
		case '+': { // 포인터가 가리키는 수를 1 증가시킨다.
			arr[p] = arr[p] == 255 ? 0 : arr[p] + 1;
			break;
		}
		
		case '<': { // 포인터를 왼쪽으로 한 칸 움직인다.
			p = p == 0 ? sm - 1 : p - 1;
			break;
		}
		
		case '>': { // 포인터를 오른쪽으로 한 칸 움직인다.
			p = p == sm - 1 ? 0 : p + 1;
			break;
		}
		case '[': { // 만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다.
			if(arr[p] == 0) { // 루프에 걸리지 않음
				codeIdx = bracket[codeIdx];
			}
			break;
		}
		case ']': { // 만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다.
			if(arr[p] != 0) { // 루프에 걸림
				codeIdx = bracket[codeIdx];
			}
			break;
		}
		case '.': { // 포인터가 가리키는 수를 출력한다.
			// 실제로는 아무일도 하지 않음
			break;
		}
		case ',': { // 문자 하나를 읽고 포인터가 가리키는 곳에 저장한다.
			arr[p] = inputIdx == si ? 255 : input[inputIdx++];
			break;
		}
		}
		codeIdx++;
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < t; tc++) {
			// 입력
			st = new StringTokenizer(br.readLine());
			sm = Integer.parseInt(st.nextToken()); // 메모리 배열 크기
			int sc = Integer.parseInt(st.nextToken()); // 프로그램 코드 크기
			si = Integer.parseInt(st.nextToken()); // 입력의 크기
			
			arr = new int[sm]; // 배열
			code = new char[sc]; // 명령
			input = new char[si]; // 입력
			
			code = br.readLine().toCharArray();
			input = br.readLine().toCharArray();
			
			// 각 괄호의 짝 인덱스 구하기
			bracket = new int[sc]; // '['의 위치에는 연결되는 ']'의 인덱스를, ']'의 위치에는 연결되는 '['의 인덱스를 저장함
			Stack<Integer> stack = new Stack<>(); // 괄호를 담아둘 스택
			for (int i = 0; i < bracket.length; i++) {
				if(code[i] == '[') stack.push(i); // 여는 괄호면 스택에 담고
				else if(code[i] == ']') { // 닫는 괄호면
					int start = stack.pop(); // 짝이 되는 여는 괄호를 꺼내고
					bracket[start] = i; // 각 인덱스에 서로의 인덱스를 저장
					bracket[i] = start;
				}
			}
			
			p = 0; // 프로그램 수행 전 포인터가 가리키는 칸은 0
			codeIdx = 0; // 실행할 명령 인덱스
			inputIdx = 0; // 다음 입력 인덱스
			int count = 0; // 명령 수행 횟수
			
			// 무한 루프에 빠지지 않고 모든 명령을 실행했거나
			// 명령을 5천만번 이상 실행했을 경우 반복문을 빠져나옴
			while(codeIdx < sc && count <= 50_000_000) {
				command();
				count++;
			}
			
			// 답 저장
			if(codeIdx == sc) sb.append("Terminates\n");
			else { // 무한루프에 빠졌다면
				/*
				 * 마지막으로 명령을 수행했던 곳에서 다시 5천만번의 명령을 수행하며 어디서 루프에 빠졌는지 확인한다.
				 * 가장 마지막 인덱스까지 간 곳이 루프의 닫는 괄호이고
				 * 가장 앞 인덱스까지 간 곳의 앞 칸이 루프의 여는 괄호 위치이다,
				 * 
				 */
				int s = codeIdx;
				int e = codeIdx;
				while(count-- > 0) { // 어디 루프에 빠졌는지 구한다
					command();
					s = Math.min(s, codeIdx);
					e = Math.max(e, codeIdx);
				}
				sb.append("Loops " + (s - 1) + " " + e + "\n");
			}
		}
		
		// 출력
		System.out.println(sb);
	}

}