백준 3954 Brainf**k 인터프리터

출처 : 백준

 

문제 해석

• 출력이 Terminates이거나 Loops x y 이기 때문에 입력의 마지막인 프로그램 입력 부분은 무시해도 무관
• [ ]이 do-while 반복문과 같이 동작함
• 50,000,000  5천만 번 이상 실행 시 종료되지 않는다면 무한루프 판정

구현이 어려운 문제는 아니었지만 골드 1 레벨인 이유는 "무한루프" 일 때 해당 구간을 정확히 구하는

마지막 처리가 까다로운 이유인 것 같다. ( 나도 이 부분에서 매우 오랜 시간 고민했다 )

 

풀이

기본적으로 탐색 시간을 최소화시키기 위해 한 쌍인 각 괄호의 위치를 pos배열에 저장하였다.

 

마지막 무한루프 위치 처리에 대해서 다양한 생각을 해보았지만 실패했다.

1. 무한루프 판정 시 실행 중인 루프를 포함한 가장 바깥의 루프 ==> + [ - [ ] + + ] 같은 반례에 걸린다.
2. 무한루프 판정 시 실행 중이던 루프가 무한루프 ==> 유한 루프를 포함한 무한루프가 있다.

결국 마지막에 해결한 방법은 약간은 무식한 방법이다.

 

출력의 제한조건의 한 문장을 단서로 하여서 무한루프 판정을 받은 코드의 경우 5천만 번을 추가적으로 실행시켜

그때 도달한 가장 바깥의 루프를 무한루프로 판정하였다.

 

코드

import java.util.*;
import java.io.*;

public class Main_BJ_Brainfook인터프리터_3954 {
	static final int mod = (int)(Math.pow(2, 8));
	static int[] memory;
	static char[] code;
	static char[] input;
	static int[] pos;
	static int count,cidx,iidx,midx;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for(int tc=0 ; tc<T ; tc++) {
			String[] tarr = br.readLine().split(" ");
			memory = new int[Integer.parseInt(tarr[0])];
			code = br.readLine().toCharArray();
			input = br.readLine().toCharArray();
			count=0; cidx=0; iidx=0; midx=0;
			// Loop 위치 배열 시작
			Stack<Integer> tmp = new Stack<>();
			pos = new int[4095];
			for (int i = 0; i < code.length; i++) {
				if(code[i] == '[')
					tmp.push(i);
				else if(code[i] == ']') {
					pos[i]= tmp.peek();
					pos[tmp.pop()] = i;
				}
			}
			// Loop 위치 배열 끝
			
			while(cidx < code.length && count <= 50000000) {
				run_program();
				count++;
			}
			int R = cidx;
			
			if(cidx < code.length && count >= 50000000) {
				while(count > 0) {
					run_program();
					R = Math.max(cidx, R);
					count--;
				}
				int L = pos[R];
				sb.append("Loops ").append(L).append(' ').append(R).append('\n');
			}
			else
				sb.append("Terminates").append('\n');
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	static void run_program() {
		char c = code[cidx];
		switch(c) {
		case '-':
			memory[midx] = (memory[midx]-1) % mod;
			break;
		case '+':
			memory[midx] = (memory[midx]+1) % mod; 
			break;
		case '<':
			midx--;
			if(midx == -1)
				midx = memory.length-1;
			break;
		case '>':
			midx++;
			if(midx == memory.length)
				midx = 0;
			break;
		case '[':
			// 포인터 위치가 0이면 ] 다음 명령어로 점프
			if(memory[midx] == 0) {
				cidx = pos[cidx];
			}
			break;
		case ']':
			// 포인터 위치가 0이 아니면 이전 [의 다음 명령어로 점프
			if(memory[midx] != 0) {
				cidx = pos[cidx];
			}
			break;
		case '.':
			break;
		case ',':
			if(iidx == input.length)
				memory[midx] = 255;
			else
				memory[midx] = input[iidx++]; 
			break;
		}
		cidx++;
	}
}