피터슨 그래프 문제란?
아래와 같은 그래프가 하나 있다고 가정해 보겠습니다. 바로 유명한 피터슨 그래프(Petersen Graph)입니다. 정점은 0부터 9까지 번호가 매겨져 있으며, 각 정점에는 특정 문자가 배치되어 있습니다.
피터슨 그래프는 외부의 5개 정점(0~4)이 오각형을 이루고, 내부의 5개 정점(5~9)이 별(pentagram) 형태로 연결되어 있으며, 각 내부 정점은 번호가 정확히 5만큼 차이 나는 외부 정점과 연결된 구조입니다.
이 그래프에서 L개의 정점을 사용하는 경로(walk) W를 생각해 봅시다. 길이가 L인 문자열 S가 경로 W로 실현(realized)된다는 것은, W를 따라 지나가면서 만나는 문자들의 순서가 S와 정확히 일치한다는 의미입니다. 이때 같은 정점을 여러 번 방문하는 것도 허용됩니다.
예를 들어 문자열 S = "ABBECCD"는 경로 (0, 1, 6, 9, 7, 2, 3)으로 실현됩니다. 우리의 과제는 주어진 문자열을 실현할 수 있는 경로를 찾는 것이며, 경로가 존재한다면 그중 사전순으로 가장 작은(lexicographically smallest) 경로를 찾는 것입니다. 만약 가능한 경로가 전혀 없다면 -1을 반환해야 합니다.
알고리즘 접근 방식
핵심 아이디어는 단순합니다. 문자열의 첫 문자로 시작 정점을 결정한 뒤, 이후 각 문자에 대해 현재 정점에서 이동 가능한 인접 정점을 찾으면 됩니다. 각 문자는 외부 정점(0~4) 또는 대응되는 내부 정점(번호 + 5) 두 가지 위치로 실현될 수 있으므로, 두 경우를 순서대로 검사합니다. 사전순으로 가장 작은 경로를 얻기 위해 먼저 외부 정점에서 시작을 시도하고, 실패하면 내부 정점에서 시작을 시도합니다.
의사 코드
시작
res := 시작 정점
S의 첫 번째 문자를 제외한 각 문자 c에 대해 반복:
만약 외부 그래프에서 v와 c 사이에 간선이 존재하면
v := c
아니면 내부 그래프에서 v와 (c + 5) 사이에 간선이 존재하면
v := c + 5
아니면
false 반환
조건문 종료
v를 res에 추가
반복문 종료
true 반환
끝
C++ 구현 예제
10×10 인접 행렬(adj_mat)로 피터슨 그래프의 연결 관계를 저장합니다. 함수 petersonGraphWalk는 시작 정점 v에서 출발하여 문자열의 각 문자를 순서대로 처리하며, 이동할 때마다 결과 배열 res에 정점 번호를 기록합니다.
#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++){
// 외부 그래프 탐색
if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
v = S[i] - 'A';
}
// 내부 그래프 확인
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
문자열 "ABBECCD"에 대해 시작 정점 0(외부)에서 출발하는 경로가 성공적으로 발견되어 0169723이 출력됩니다. main 함수에서는 먼저 외부 정점(str[0] - 'A')에서 시작을 시도하고, 실패할 경우에만 내부 정점(str[0] - 'A' + 5)에서 다시 시도함으로써 사전순으로 가장 작은 경로를 보장합니다.
복잡도 분석
문자열의 길이를 L이라 하면, 각 문자마다 상수 시간 안에 이동할 정점을 결정하므로 전체 시간 복잡도는 O(L)입니다. 공간 복잡도 역시 결과를 저장하기 위한 O(L)입니다.