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

BOJ 3954 Brainf**k 인터프리터

문제풀이

너무너무너무 어려웠다. 정말 많은 고난과 역경을 겪은 문제다. 하다보면 구현은 대충 다 된다. 이 문제의 어려운 점은 '반복문을 어떻게 처리하는가'다.

• 5천만번의 반복이 아니라 5천만번의 명령 수행이다.
• 스택을 이용하여 먼저 반복문 짝 모두 찾아두기

짝을 먼저 찾아두면 명령어를 실행하는 switch문 안에서 [ 과 ]를 만났을 때 간단해진다. 동시에 [ 을 만났을 때는 시작점을 기록하고 ] 을 만났을 때는 종료점을 기록하도록 하였는데 주어진 테스트 케이스는 통과하지만 제출하면 틀린다.

• 바깥쪽 반복문이 무한루프인데 안쪽 반복문을 실행하다 명령 수행 횟수가 5천만이 넘어서 안쪽 반복문을 무한루프로 저장될 수 있다.
• 여기서 개인적으로 이 문제의 하이라이트 아이디어가 등장한다. 바로 무한루프 찾기
  무한루프가 존재한다는 것은 우리가 코딩하다 종종 마주치는 unreachable code 가 존재한다는 것이다. 따라서 무한루프의 끝점 이후에는 명령어가 전혀 실행되지 않는다. 이 점을 이용해 다음과 같은 코드를 구현할 수 있다.

    private static void findLoops() {
      for (int i = Sc - 1; i >= 0; i--) {
        if (touch[i] > 0) {
          System.out.println(loop[i] + " " + i);
          break;
        }
      }
    }

- 명령어가 실행될 때 마다 해당 명령어의 실행 횟수를 `++`한다. 이 문제에서는 반복문의 시작과 끝에 대해서만 실행 횟수를 저장해주면 된다.
- **명령어의 가장 끝 부터 순차 탐색하여 명령어가 처음으로 실행된적 있는 부분을 만나면 그 부분이 무한루프의 마지막 부분이다.**

구현코드

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

public class Main {
	
	static final int INFINITE = 50000000;
	static final int MAX = 256;
	
	static int[] memory;
	static int[] loop;
	static int[] touch;
	static char[] cmd;
	static char[] input;
	
	static int loopStart, loopEnd, cmdCnt;
	
	static int p;
	static int cp;
	static int ip;
	
	static int T, Sc, Sm, Si;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = stoi(br.readLine());
		
		for(int t = 0 ; t < T ; ++t) {
			init(br);
			
			while(cmdCnt < INFINITE && cp < Sc) {
				cmdCnt++; // 명령어 실행 횟수 증가 
				switch(cmd[cp]) {
				case '-':
					memory[p] = (memory[p] + 255) % MAX;
					break;
				case '+':
					memory[p] = (memory[p] + 1) % MAX;
					break;
				case '<':
					p = (p + (Sm - 1)) % Sm;
					break;
				case '>':
					p = (p + (Sm + 1)) % Sm;
					break;
				case '[':
					if(memory[p] == 0) {
						cp = loop[cp];
						continue;
					}
					break;
				case ']':
					if(memory[p] != 0) {
						touch[cp]++;
						cp = loop[cp];
						continue;
					}
					break;
				case '.':
					// memory[p] 출력 
					break;
				case ',':
					// input을 memory에 입력하기
					// input의 마지막을 넘은 경우 255 입력 
					if(ip == Si) {
						memory[p] = 255;
					} else {
						memory[p] = input[ip++];
					}
					break;
				}
				cp++; // 명령어 포인터 증가
			}
			
			if (cmdCnt == INFINITE) {
				System.out.print("Loops ");
				findLoops();
			} else {
				System.out.println("Terminates");
			}
		}
		
	}
	
	private static void findLoops() {
		for (int i = Sc - 1; i >= 0; i--) {
			if (touch[i] > 0) {
				System.out.println(loop[i] + " " + i);
				break;
			}
		}
	}

	private static void init(BufferedReader br) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		Sm = stoi(st.nextToken());
		Sc = stoi(st.nextToken());
		Si = stoi(st.nextToken());
		
		memory = new int[Sm];
		loop = new int[Sc];
		touch = new int[Sc]; // 반복문 명령어가 수행된 횟수
		cmd = br.readLine().toCharArray();
		input = br.readLine().toCharArray();
		
		Stack<Integer> stack = new Stack<>();
		
		// 반복문 짝 만들기 
		for(int i = 0 ; i < Sc ; ++i) {
			if(cmd[i] == '[') stack.push(i);
			else if(cmd[i] == ']') {
				int start = stack.pop();
				loop[start] = i;
				loop[i] = start;
			}
		}
		
		loopStart = 0;
		loopEnd = 0;
		cmdCnt = 0; // 명령어 수행횟수 
		
		p = 0; // 메모리 포인터 
		ip = 0; // 인풋 포인터 
		cp = 0; // 커맨드 포인터 
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}