Piet은 프로그래밍 언어의 하나로, 코드가 N×M의 2차원 이미지로 되어 있는 것이 특징이다. 이름의 유래는 추상화로 유명한 네덜란드의 화가인 피트 몬드리안(Piet Mondrian)이다. 다음의 이미지는 "Hello, world!"를 출력하는 Piet 코드이다.

Piet 프로그램에서 단위 정사각형을 코델(Codel)이라고 하며 각 코델마다 특정 색깔이 칠해져있다. 이는 비트맵 이미지의 픽셀에 대응되는 개념이다. 같은 색깔의 코델이 상하좌우로 연결된 블록이 프로그램의 최소 실행 단위가 된다. 맨 처음 실행되는 블록은 가장 왼쪽 위 코델이 포함된 블록이며, 규칙에 따라 다음에 실행될 블록으로 이동하는 과정을 반복한다.

현재 블록에서 어떤 블록으로 이동할지를 결정하기 위해 DP(Direction Pointer)와 CC(Codel Chooser)라는 두 가지 값이 존재한다. DP의 값은 왼쪽, 오른쪽, 위쪽, 아래쪽 중 하나이고, CC의 값은 왼쪽 혹은 오른쪽 중 하나이다. 프로그램이 처음 실행될 때 DP의 값은 오른쪽, CC의 값은 왼쪽이다. 어떤 블록으로 이동할지를 선택하는 기준은 다음과 같다.

현재 블록의 코델들 중에서 DP의 방향으로 가장 멀리 위치한 코델들을 찾는다. 블록이 볼록하지 않은 경우 이 코델들은 연속하지 않을 수 있다.

위에서 찾은 코델들 중 DP 방향을 향했을 때 CC의 방향으로 가장 끝에 있는 코델을 선택한다. 이 때 CC의 방향은 상대적인 방향임에 유의하라. 예를 들어, DP가 아래쪽을 가리키고 CC가 오른쪽을 가리키는 경우, 선택되는 코델은 가장 왼쪽에 있는 코델이 된다.

위에서 선택한 코델에서 DP의 방향으로 맞닿은 코델이 포함된 블록이 다음 블록이 된다.

이에 대한 예시로, 다음과 같은 그림에서 어떤 블록으로 이동할지를 선택하는 과정을 살펴보자.

각 칸에 적힌 글자는 색깔을 나타내는 값이다. 현재 블록은 A 블록이고, DP의 값(검은 화살표)은 아래쪽, CC의 값(회색 화살표)은 오른쪽인 상태이다. 이 때 A 블록의 코델들 중에서 DP의 방향으로 가장 멀리 위치한 코델은 A 블록에서 가장 아래쪽에 위치한 코델로, 그림에서 점으로 표시된 코델이다. 이 블록들 중 CC의 방향으로 가장 끝에 있는 코델은 그림에서 테두리로 표시된 블록이다. 이 코델의 아래쪽(DP의 방향)으로 맞닿은 코델(빨간색 별표)이 속한 블록인 B 블록이 다음 블록이 된다.

검은색 블록 혹은 이미지의 경계 바깥은 이동할 수 없는 구역이다. 만약 다음으로 이동하려는 블록이 검은색이거나 이미지의 경계를 벗어나는 경우는 다음의 방법으로 진행한다.

CC의 값이 왼쪽인 경우 오른쪽으로, 오른쪽인 경우 왼쪽으로 바꾼 후 다시 이동을 시도한다.
CC의 값을 바꾼 후에도 이동할 수 없는 경우, CC의 값을 유지하며 DP를 시계방향으로 회전한 후 다시 이동을 시도한다.
시계방향으로 회전한 후에도 이동할 수 없는 경우, 1번으로 되돌아간다.
위 과정을 계속 반복하여 총 8가지의 경우를 모두 시도했는데도 이동할 수 있는 블록을 찾지 못한 경우, 프로그램이 종료된다.

예를 들어, 다음과 같은 그림에서 어떤 블록으로 이동할지를 선택하는 과정을 살펴보자.

현재 블록은 A 블록이고, DP의 방향은 위, CC의 방향은 왼쪽인 상태이다. 이번에도 경계에 위치한 코델을 점으로, CC에 의해 선택된 코델을 테두리로 표시하였다. 현재 상태에서 선택된 다음 블록은 검은색 블록이므로 이동할 수 없다. 따라서 CC의 값을 오른쪽으로 바꾼 뒤 다시 다음 블록을 찾는데, 역시 검은색 블록이므로 이동할 수 없다. 이제 DP의 방향을 시계방향으로 회전하여 오른쪽으로 바꾼 뒤 블록을 찾는다(이 때 CC의 값은 바뀌지 않는다). 선택된 코델과 맞닿은 블록은 이미지의 경계 밖이므로 CC의 값을 왼쪽으로 바꾼 뒤 다시 시도한다. 이번에는 다른 코델이 선택되지만 역시 맞닿은 블록이 이미지의 경계 밖이므로 이동할 수 없다. 다시 DP의 방향을 시계방향으로 회전하여 아래로 바꾼 뒤 블록을 찾는다. 이 때 선택된 블록은 검은색 블록으로 역시 이동할 수 없고, CC의 값을 다시 오른쪽으로 바꾸면 B 블록이 선택되고 이는 이동할 수 있는 블록이다. 따라서 다음 블록은 B 블록이 된다. 이상의 과정을 그림으로 나타내면 다음과 같다.

Piet으로 작성된 프로그램이 주어졌을 때, 이 프로그램이 어떤 블록을 거치며 실행되는지 알고 싶어졌다. 입력된 Piet 프로그램에 대해, 프로그램이 종료할 때까지 거치는 블록의 색깔을 출력하는 프로그램을 작성하시오.

* 실제 Piet의 연산 중에는 픽셀의 색깔에 따라 DP 혹은 CC가 바뀌는 연산이 있지만, 이 문제에 한해서는 위에서 설명된 규칙에 의해서만 DP와 CC가 변경되는 것으로 간주한다.

#3549 upload 27 done 6 how_to_reg 6

Piet timer 1s memory 512MB

#3549

Piet 1s 512MB