20.07.27 - 무어기계(cont)

https://www.acmicpc.net/problem/3300

3300번: 무어 기계

대략적인 가닥은 잡혔는데 핵심적인 부분의 방식을 아직 구상하지 못하고 있습니다.

우선 대략적인 부분.

입력된 무어 머신을 앞에서부터 순회합니다.

그리고 Spells Vector와 Index Vector로 나누어서 관리합니다.

Spells는 무어머신에 입력된 Alphabat. 즉 State의 저장입니다.

중복된 알파뱃이 입력될 수 있으므로 이를 따로 관리하기 위해 Vector로 관리를 합니다.

 

그리고 이 State들간의 관계. 즉 Condition을 최대한 가볍게 구현하기 위해 Vector<Vector<int>>를 추가했습니다.

이 Vector는 Index값으로 State들간의 관계를 나타냅니다.

선행 State와 후행 State가 일대다 관계도, 다대일 관계도 가능하기에
어쩔 수 없이 이차원 Vector를 사용해야 할 것 같습니다.

 

무어 머신을 순회하면서 Alphabat이 들어오면 기본적으로 선행 Alphabat의 Index Vector에 값이 추가됩니다.

단, Alphabat이 아닌 특수 문자가 들어올 때에는 특수한 작업이 발생합니다.

이 때 문제가 발생합니다.

 

) 문자가 들어온 이후의 첫 Alphabat은 선행 State들과 연결을 지어야 합니다.

이것이 가능하려면 선행 Alphabat이 어디부터 어디까지인지 판단을 할 수 있어야 합니다.

그런데 이를 판단하는 방식을 아직 구상하지 못했습니다.

 

우선은 height Vector를 먼저 도입해볼까 합니다.

현재 Alphabat과 인접한 Alphabat과 같은 Height를 지닌 연속적인 모든 Alphabat을

선행 Alphabat으로 판정하는 것입니다.

 

그 이후에 형성된 그래프를 순회하는 것도 고민을 해봐야 할 것 같습니다.