[BOJ] 백준 3954번 : Brainf**k 인터프리터 (JAVA)

문제

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

 

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

 

 

 

 

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

 

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

 

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

 

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

 

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

 

 

입력

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

 

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

 

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

 

 

출력

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([와 ]의 위치)

 

프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

 

 

풀이 (구버전 - 틀린 풀이)

괄호 처리가 꽤 까다로웠던 시뮬레이션 문제였습니다. [, ]를 제외한 나머지 기호는 말그대로 시키는 대로 구현을 하면 되기때문에 크게 어려운 부분이 없었다고 생각합니다. 다만, 범위 처리에 유의하셔야 했습니다. 포인터가 가리키는 구간은 [0, 배열의 크기)인데, 이를 넘어가면 적절히 숫자를 맨 처음과 맨 끝으로 보내는 과정을 거치면 됩니다.

 

 

자, 이제 무한루프인지 확인을 어떻게 해야할 지 알아봅시다.

먼저, 여는 괄호와 닫는 괄호는 서로 쌍이 맞아야하기때문에 스택을 이용하여 여는 괄호와 닫는 괄호의 연결성을 만들어 줍니다. 아래 코드를 보면서 이해해 봅시다.

 

 

Stack<Integer> stack = new Stack<>();
int[] bracket = new int[Sc]; // 서로 연결되어있는 괄호의 위치.
for (int i = 0; i < Sc; i++) {
    char c = programCode.charAt(i);
 
    if (c == '[') {
        stack.push(i);
    } else if (c == ']') { // 닫는 괄호와 여는 괄호를 서로 연결시켜 줌.
        int temp = stack.peek();
        bracket[i] = temp; // 여는 괄호에는 닫는 괄호의 위치를
        bracket[temp] = i; // 닫는 괄호에는 여는 괄호의 위치를 저장함.
        stack.pop();
    }
}

 

 

스택에는 여는 괄호만 push를 합니다. 그리고 닫는 괄호는 만났을 때 stack에서 peek()을 한 값이 여는 괄호이므로 bracket라는 1차원 배열에 "bracket[여는 괄호의 위치] = 닫는 괄호의 위치" 혹은 "bracket[닫는 괄호의 위치] = 여는 괄호의 위치"의 관계를 갖도록 만들어줍니다. 인접리스트에서 양방향 인접리스트를 만드는 느낌과 유사합니다.

 

이렇게 되면, 각 괄호마다 짝꿍(?)이 어디에 위치하는지 알 수 있게 됩니다.

 

그리고 이를 이용하면 괄호 명령어를 쉽게 다룰 수 있습니다. 이에 대해서도 아래 코드를 보면서 이해해 봅시다.

 

 

case '[':
    if (arr[pointerPos] == 0) {
        i = bracket[i]; // 현재 위치를 닫는 괄호의 위치로 점프함.
    }
    break;
 
case ']':
    if (arr[pointerPos] != 0) {
        // 닫는 위치의 최댓값을 구하는 이유.
        // 무한루프가 돈다는 의미는 어떠한 위치에서 앞쪽으로 계속 왔다갔다한다는 의미이므로
        // 무한루프가 돌지 않는다면, 닫는 괄호의 위치는 점점 뒤쪽으로 가게 될 것임.
        maxCloseBracket = Math.max(maxCloseBracket, i);
        i = bracket[i]; // 현재 위치를 여는 괄호의 위치로 점프함.
   }
    break;

 

 

여는 괄호에서는 단순히 닫힌 괄호의 위치로 점프하면 됩니다. 그리고 닫는 괄호에서도 여는 괄호의 위치로 점프하면 됩니다. 다만, 문제에서 무한루프가 발생하는 경우, 어디서 발생했는지도 위치를 찍으라고 명시하였습니다.

 

이를 위하여 닫힌 괄호의 최대 위치를 구했습니다. 이유는 간단합니다. 무한루프가 돈다는 의미는 어떠한 위치에서 앞쪽으로 갔다가 뒤쪽으로 갔다가하는 행위를 반복하는 것이므로 무한루프가 발생하지 않을 경우, 닫힌 괄호는 점점 뒤쪽으로 가게 될 것입니다.

 

따라서, 위와 같이 switch문을 구성하고 명령어의 반복 횟수가 5천만이 되면 무한루프가 발생한 것으로 판단하여 "Loop " + "여는 괄호의 위치 " + "닫힌 괄호의 위치\n"를 출력하고 종료하고, 그렇지 않으면 "Terminates"를 출력하고 종료하면 됩니다.

 

 

풀이 (신버전 - 올바른 풀이)

이 문제는 약 일주일 전에 재채점되었고, 많은 사람들이 위와 같은 풀이를 작성하여 틀렸습니다. 저 또한 틀렸고 반례를 도무지 찾을 수 없었습니다. 그러다가 백준 질문 게시판에서 힌트를 얻었습니다.

 

위의 풀이에서는 "방문한 닫힌 괄호 중 가장 뒤에 있는 괄호를 찾는다."는 로직을 사용하였습니다. 하지만, 이때 반례가 있습니다.

 

배열의 사이즈가 1이고, 명령어가 "++[[++]+]"일 때 무한 루프는 (3, 6)이 정상이지만, 제 로직대로 수행하면 (2, 8)이 나옵니다. 따라서 "방문한 닫힌 괄호 중 가장 뒤에 있는 괄호를 찾는다."는 방식은 틀렸습니다.

 

그렇다면, 어떻게 하는 것이 좋을까요? 여러 가지 방법이 있을듯한데, 가장 확실한 방법은 시행 횟수를 2배로 하여 검사하는 것입니다. 아래 내용을 찬찬히 봅시다.

 

 

먼저, 특정 명령어의 위치를 가리키는 pid라는 변수를 정의합시다. 명령어가 "+-<>"이고, 만약 pid가 2라면 명령어 "<"를 가리키고 있는 셈입니다.

 

그리고 pid를 증가하거나, 괄호의 위치에 따라 이동하면서 루프를 쭉쭉 돌립니다. 만약, pid가 EOF에 도달한다면 정상 출력을 하고, 그렇지 않고 50,000,000번 연산을 반복한다면 일단 빠져 나옵니다.

 

그렇다면 pid는 어떤 괄호와 괄호 사이의 위치할 것입니다. (딱 괄호의 위치에 있을 수도 있습니다.)

그리고 여는 괄호의 위치를 maxPid, 닫는 괄호의 위치를 minPid라고 합시다. 이 두 가지 변수를 pid라고 초기화해 놓고, 다시 그 위치에서 50,000,000번 연산을 시킵니다.

 

이 과정에서 maxPid = max(pid, maxPid), minPid = min(pid, minPid)로 연산합니다. 그렇다면, maxPid는 닫는 괄호의 위치가 되고 (minPid - 1)은 여는 괄호의 위치가 됩니다. 여는 괄호의 위치가 minPid가 아닌, (minPid - 1)이 되는 이유는 닫는 괄호에서 여는 괄호로 이동한 후 바로 한 칸 이동하기 때문입니다.

 

그리고 이 값들을 각각 출력해 주면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.