문제1121--State transition diagram II

1121: State transition diagram II

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

다음은 "프로세스 상태 전이 다이어그램" 이다

  • 박스 안의 글자는 각 프로세스의 상태를 가리키며, 화살표의 글자는 명령을 나타낸다.
  • 한 상태에서 다른 상태로의 전이는 화살표로 연결된 명령에 의해서만 가능하다. ex) READY 상태에서는 dispatch 명령을 통해 RUNNING 상태로 전이가 가능하며, suspend 명령을 통해 READY/SUSPEND 상태로 전이가 가능하다.
  • 화살표로 연결되지 않은 명령은 사용할 수 없다. ex) READY 상태에서는 release 명령을 수행할 수 없다.
  • 초기 상태는 NEW 에서 시작한다.


순차적으로 실행되는 명령이 주어졌을 때 프로세스의 최종 상태를 출력하는 프로그램을 작성하시오. 만약, 상태 전이가 불가능하다면 IMPOSSIBLE 을 출력합니다.

입력 설명

첫 줄에는 테스트 케이스 개수 T가 주어진다. (1 <= T <= 50)

각 테스트 케이스마다 첫 번째 줄에 명령의 개수 K가 주어지고, 다음 줄에 K개의 명령 리스트가 스페이스로 구분되어 주어진다. (1 <= K <= 10)


출력 설명

각각의 테스트 케이스에 대해서 한 줄로 상태 전이가 가능하다면 최종 상태를, 상태 전이가 불가능하다면 IMPOSSIBLE 을 출력한다. 만약, 전이 가능한 최종 상태가 여러 개일 경우에는 사전순으로 먼저오는 것을 출력한다.

입력 예시 Copy

3
2
admit activate
2
admit dispatch
4
admit dispatch suspend release

출력 예시 Copy

READY
RUNNING
IMPOSSIBLE

출처/분류