아래와 같은 그래프가 하나 있다고 가정합니다. 그 그래프는 Peterson 그래프입니다. 정점은 0에서 9까지 번호가 매겨져 있습니다. 각 정점에는 몇 개의 문자가 있습니다. L 정점이 사용되는 그래프에서 W를 한 번 살펴보겠습니다. L 문자가 있는 문자열 S는 W와 S의 문자 시퀀스가 같을 때 보행시선 W에 의해 실현됩니다. 정점을 여러 번 방문할 수 있습니다.
예를 들어, 하나의 문자열 S는 "ABBECCD"와 같으며 걷기(0, 1, 6, 9, 7, 2, 3)로 구현됩니다. 우리의 임무는 그러한 걷기를 찾는 것이며, 그 걷기가 존재한다면 사전순으로 가장 적은 걷기를 찾는 것입니다. 빨기 걷기가 없으면 -1을 반환합니다.
알고리즘
PetersonGraphWalk(S, v) -
begin res := starting vertex for each character c in S except the first one, do if there is an edge between v and c in outer graph, then v := c else if there is an edge between v and c+5 in inner graph, then v := c + 5 else return false end if put v into res done return true end
예시
#include<iostream> using namespace std; bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0} }; char S[100005]; char res[100005]; bool petersonGraphWalk(char* S, int v){ res[0] = v + '0'; for(int i = 1; S[i]; i++){ //traverse the outer graph if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){ v = S[i] - 'A'; } //then check the inner graph else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){ v = S[i] - 'A' + 5; }else{ return false; } res[i] = v + '0'; } return true; } main() { char* str = "ABBECCD"; if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){ cout << res; }else{ cout << -1; } }
출력
0169723