<Baekjoon> #3954 Brainf**k 인터프리터_Simulation, Stack java

#3954 BrainF**k 인터프리터

Solution

문제가 단순해 보이는데 이해하는데 꽤 오랜 시간이 걸렸다..

• 문제는 프로그램이 주어졌을 때, 이 프로그램이 끝나는지 아니면 무한루프에 빠지게 되는지 구하는 것이고, 무한루프에 빠졌을 때는 어느 부분이 무한루프인지를 출력하는 문제다
• 프로그램이 최대로 수행될 수 있는 횟수는 50,000,000번(이하 오천만) 이며 오천만번 이상 수행된 경우 프로그램은 항상 종료되거나 무한 루프에 빠져있다
• 무한 루프일 경우 해당 루프는 적어도 한 번 실행이 완료된 상태이며 한 번의 루프에서 실행되는 명령어의 개수는 오천만 번 이하이다

예를들어 문제에서 프로그램의 명령어 입력으로 +-.,[[]] 와 같은 입력이 들어왔다고 하면 먼저 0번 째 인덱스부터 살펴본다
+부터 보고 이 때 이 명령어가 의미하는대로 진행을 한다. 진행을 하는 도중 index는 계속 바뀌고 3번째 인덱스가 가리키는 명령어를 수행하다가 다시 0번째로 돌아올 수 있고 이런 식으로 반복한다 -> 따라서 programIdx를 두어 매번 실행되는 횟수를 체크하고 이 횟수가 오천만 번을 넘으면 무한 루프에 빠진 상태이고 그렇지 않다면 Terminated 된 것이다

이때 중요하게 짚고 넘어가보아야 할 점이 위에서 언급했던 이 부분이다

무한 루프일 경우 해당 루프는 적어도 한 번 실행이 완료된 상태이며 한 번의 루프에서 실행되는 명령어의 개수는 오천만 번 이하이다

이 말은 오천만 번 명령어를 수행한 후 무한 루프에 들어왔을 때 안에 최대 오천만 번의 명령어가 또 있을 수가 있다. 그래서 총 오천만 번*2=1억번만큼 실행할 수 있다는 의미이다.

무한 루프

• 무한 루프의 정의 : 두 개의 루프가 겹쳐져 있을 때 무한 루프는 과연 무엇일까?
  [[]] 다음과 같은 무한 루프가 있다고 할 때, 무한 루프는 [[]]이 아니라 []이다.
  안에 있는 괄호 []가 무한히 반복된다고 가정할 때, [...A...[...B...]...C...]에서 B영역이 무한히 반복된다면 A,C는 빠져나가지도 않지만 무한히 반복되지도 않는 상태가 된다

• 문제에서 실행하다가 오천만 번 이상 프로그램이 진행되고 있다면 매번 루프가 시작되는 인덱스 (loopStartIdx)를 현재 명령어의 인덱스와 비교해 최소값으로 갱신해준다 (문제에서 구해야 하는 값은 이 무한루프가 언제부터 시작되었는가! 이므로)

변수 선언

	static final int MAX= (int) (5*1e7);
	static final int DATA_MAX=(int)(1e5+100);
	static final int MOD=256;
    
    static int T, sm, sc, si;				//테스트 케이스, 배열의 크기, 코드 크기, 입력 크기
	static String program, input;
    static HashMap <Integer, Integer> map=new HashMap<>();	//[] 괄호 쌍을 저장
    
    int idx=0;								//포인터
	int programIdx=0;						//현재까지 프로그램이 몇 번 실행되었는지 확인
	int inputIdx=0;							//입력 문자를 읽고 저장해야하는 경우가 있음
	int loopStartIdx=Integer.MAX_VALUE;		//제일 최근에 돌았던 루프의 Index를 저장하고 있음
	boolean isTerminated=true;
    
    int[] datas = new int[DATA_MAX];		//데이터 배열

Loop 쌍 만들기

• 문제에서 [ 혹은 ] 이 들어왔을 경우, 짝을 이루는 괄호의 명령의 위치를 알아야 한다
• hash map에 각 쌍을 저장하고, 이때 열린 괄호의 인덱스를 알면 닫힌 괄호의 인덱스를 알 수 있고, 닫힌 괄호의 인덱스를 알면 열린 괄호의 인덱스를 알 수 있도록 만들어 준다
  
• 열린 괄호가 들어왔을 때, 스택에 인덱스를 push하고 닫힌 괄호가 들어왔을 때는 스택에 있는 값을 pop해서 이와 쌍을 만들어 준다

static HashMap <Integer, Integer> map=new HashMap<>();
Stack <Integer> stack=new Stack<>();
			
for (int i=0; i<sc; i++) {
	if (program.charAt(i)=='[')
		stack.add(i);
				
	else if (program.charAt(i)==']') {
		int j=stack.pop();
		map.put(j, i);
		map.put(i, j);
	}
}

명령어 실행

아래에서 주어진 것과 같이 명령어를 실행한다
이때 포인터를 왼쪽이나 오른쪽으로 움직일 때, 데이터 배열의 범위를 넘어간다면 반대쪽으로 넘어간다고 되어 있으므로 -, <연산을 수행할 때 포인터가 가리키는 곳이 음수가 되지 않도록 설정해준다

(참고로 나는 ,에 대한 설명이 좀 모호하다고 생각되었다..)

명령어 실행 코드

switch (c) {
				
//포인터가 가리키는 수를 1감소
case '-': datas[idx]=(datas[idx]+MOD-1)%MOD;
	break;
    
//포인터가 가리키는 수를 1증가
case '+': datas[idx]=(datas[idx]+1)%MOD;
	break;
    
//포인터를 왼쪽으로 한 칸 움직임
case '<': idx= (idx+sm-1) % sm;
	break;
    
//포인터를 오른쪽으로 한 칸 움직임
case '>': idx= (idx+1)%sm;
	break;
    
//만약 포인터가 가리키는 수가 0이라면 [와 짝을 이루는 ] 다음 명령으로 점프
case '[': if (datas[idx]==0) i=map.get(i);
	break;
    
//만약 포인터가 가리키는 수가 0이 아니라면 ]와 짝을 이루는 [의 다음 명령으로 점프
case ']': if (datas[idx]!=0) i=map.get(i);
	break;
    
//포인터가 가리키는 수를 출력
case '.': //System.out.println(datas[idx]);
	break;
    
//문자 하나를 읽고 포인터가 가리키는 곳에 저장
//입력의 마지막인 경우 255저장
case ',' : datas[idx]= (inputIdx==si) ? MOD-1 : (int)input.charAt(inputIdx++);
	break;	
}

종료조건 코드

오천만 번을 넘을 때부터는 loopStartIdx를 매번 최소값으로 갱신해주고, 일억번 을 넘었을 때는 정상 종료되지 않은 상태로 프로그램을 끝낸다

if (++programIdx>MAX) {
	loopStartIdx=Math.min(loopStartIdx, i);
}
if (programIdx>MAX*2) {
	isTerminated=false;
	break;
}

전체 코드

package simulation;

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

public class BOJ3954 {
	
	static final int MAX= (int) (5*1e7);
	static final int DATA_MAX=(int)(1e5+100);
	static final int MOD=256;
	
	// sm: 배열 크기, sc: 프로그램 코드 크기, si: 입력 크기
	static int T, sm, sc, si;
	static String program, input;
	
	static HashMap <Integer, Integer> map=new HashMap<>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=null;
		
		T=Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			
			map.clear();
			
			st=new StringTokenizer (br.readLine());
			sm=Integer.parseInt(st.nextToken());
			sc=Integer.parseInt(st.nextToken());
			si=Integer.parseInt(st.nextToken());
			
			program=br.readLine();
			input=br.readLine();
				
			
			// loop 쌍을 만들어 줌
			Stack <Integer> stack=new Stack<>();
			
			for (int i=0; i<sc; i++) {
				if (program.charAt(i)=='[')
					stack.add(i);
				
				else if (program.charAt(i)==']') {
					int j=stack.pop();
					map.put(j, i);
					map.put(i, j);
				}
			}
			
			int idx=0;
			int programIdx=0;
			int inputIdx=0;
			int loopStartIdx=Integer.MAX_VALUE;
			boolean isTerminated=true;
			
			int[] datas = new int[DATA_MAX];
			
			for (int i=0; i<sc; i++) {
				
				char c=program.charAt(i);
				
				switch (c) {
				
				//포인터가 가리키는 수를 1감소
				case '-': datas[idx]=(datas[idx]+MOD-1)%MOD;
					break;
				//포인터가 가리키는 수를 1증가
				case '+': datas[idx]=(datas[idx]+1)%MOD;
					break;
				//포인터를 왼쪽으로 한 칸 움직임
				case '<': idx= (idx+sm-1) % sm;
					break;
				//포인터를 오른쪽으로 한 칸 움직임
				case '>': idx= (idx+1)%sm;
					break;
				//만약 포인터가 가리키는 수가 0이라면 [와 짝을 이루는 ] 다음 명령으로 점프
				case '[': if (datas[idx]==0) i=map.get(i);
					break;
				//만약 포인터가 가리키는 수가 0이 아니라면 ]와 짝을 이루는 [의 다음 명령으로 점프
				case ']': if (datas[idx]!=0) i=map.get(i);
					break;
				//포인터가 가리키는 수를 출력
				case '.': //System.out.println(datas[idx]);
					break;
				//문자 하나를 읽고 포인터가 가리키는 곳에 저장
				//입력의 마지막인 경우 255저장
				case ',' : datas[idx]= (inputIdx==si) ? MOD-1 : (int)input.charAt(inputIdx++);
					break;	
				}
				
				if (++programIdx>MAX) {
					loopStartIdx=Math.min(loopStartIdx, i);
				}
				if (programIdx>MAX*2) {
					isTerminated=false;
					break;
				}
			}
			
			if (isTerminated) 
				System.out.println("Terminates");
			else {
				System.out.println("Loops "+loopStartIdx+" "+map.get(loopStartIdx));
			}
		}
	}

}

Reference
https://www.acmicpc.net/board/view/50721
https://jaimemin.tistory.com/1536