[Hard] LexSmallestTour

문제에서 원하는 경로는 i번째와 i+1번째에 이용한 간선의 알파벳은 달라야 하지만 맨 처음과 맨 마지막에 이용한 간선의 알파벳은 같아도 된다. 예외가 있는 꼴이다. 이것을 뭔가 일반화된 꼴로 변환해 처리할 수는 없는지 생각해볼만하다. 문제에서 원하는 경로를 normal tour 라고 부르고 여기에 다음과 같은 조건을 추가한 경로를 perfect tour 라고 부르자. - 처음과 마지막에 이용한 간선의 알파벳도 달라야 한다. 주어진 그래프에서는 normal tour 랑 perfect tour 랑 별 관련이 없어보인다. 그래프에 노드 2개를 추가로 붙여 새로운 그래프를 만들어보자. # n----0 | / $| /@ | / n+1 노드n과 노드n+1을 새로 추가하고 0<->n , n<->n+1 , n+1<->0 3개의 간선을 추가했다. 간선에 붙은 문자는 기존에 있는 문자들과는 전혀 다른 문자들이다. 이렇게 생긴 새로운 그래프에서는 perfect tour가 존재하면 normal tour도 존재한다. perfect tour를 하나 찾은 뒤 0,n,n+1 로 이루어진 사이클만 제거하면 되기 때문이다. 어떤 그래프에서 perfect tour 가 존재할 조건은 다음과 같다. - 모든 정점의 차수가 짝수 - 차수가 1이상인 정점은 전부 하나의 연결 컴포넌트를 이루어야 한다. - 정점 u의 차수를 deg[u]라 하고 u에 연결된 알파벳이 c인 간선의 수를 cnt(u, c)라 하면 모든 u, c 에 대해 cnt(u, c) <= deg[u] / 2 를 만족해야한다. 첫번째, 두번째 조건은 eulerian tour 가 존재할 조건이니 자명하다. 이 상태에서 세번째 조건을 만족하면 perfect tour가 존재한다. 증명을 아주 간략하게 해보면 이렇다. 첫번째, 두번째 조건에 의해 eulerian tour 가 존재한다. 그걸 하나 찾는다. 중간에 같은 알파벳이 적힌 간선을 두번 연속 이용하는 부분이 있을 텐데 두 간선과 연결된 정점 u에는 세번째 조건에 의해 다른 알파벳이 적힌 간선이 최소한 2개 이상 존재한다. 따라서 연결된 사이클을 뒤집으면 같은 알파벳 간선을 두번 연속으로 이용하는 부분을 항상 없앨 수 있다. 이제 주어진 그래프에 normal tour 가 존재하는지는 알 수 있다. 사전순으로 가장 앞에 있는 tour 는 대체 어떻게 찾아야 할까? 사전순으로 가장 빠른 것을 찾을 때 다음과 같은 전략을 써볼 수 있다. 현재 상태에서 사전순으로 가장 빠른 선택을 한 후 그 상태에서 나머지를 갖고 답이 만들어질 수 있는지 조건을 확인한다. 답이 존재한다면 그 선택을 통해 다음 상태로 나아가고 답이 존재하지 않으면 그 다음 선택으로 넘어간다. 이 문제에서도 마찬가지이다. 현재 0번 정점에서 시작해 i번 정점까지 경로를 만든 상황이다. 지나온 경로에 속한 간선들은 모두 삭제된 상태 i와 연결된 j를 사전순으로 하나씩 고른 후 j에서 0번까지 normal tour 가 존재하는지 확인하면 된다. 확인하는 방법은 위에서 perfect tour 로 변환할 때와 비슷하게 할 수 있다. i j~~~~~~~0 | | #| |@ | $ | n------n+1 먼저 i<->j 간선을 끊고 위 그림처럼 정점 2개를 새로 추가하고 j<->n , n<->n+1 , n+1<->0 3개의 간선을 추가한다. 간선에 붙은 문자는 기존에 있는 문자들과는 전혀 다른 문자들이다. 이 상태에서 perfect tour 가 존재하는지 조건을 확인한다. perfect tour 가 존재한다면, j에서 0으로 가는 normal tour도 존재한다. 위와 같은 확인을 매 단계마다 하면서 경로를 만들어나가면 된다. 시간복잡도는 대략 O(E*E*V)