[문제]
어떤 도시 NASUP에서 국제적인 철인 마라톤(iron marathon) 대회가 열린다. 이 대회는 기존 42.195km를 달리는 일반적인 마라톤과 다르게 개최지 도시가 제공할 수 있는 최대한의 거리를 달린 후 다시 출발점으로 돌아온다. 따라서 도시에 따라서 이 달려야 하는 거리는 매해 달라진다. 우리는 NASUP시의 지도를 받아서 가장 긴 마라톤 코스를 설계해야 한다. 도로망은 edge에 가중치가 있는 단순 그래프(simple graph) 형식으로 제공된다. 두 교차로(vertex)를 지나는 도로(edge) 길이는 모두 정수(km)이다. 여러분은 경기장 ‘a’ 에서 출발하여 다시 그 장소로 되돌아오는 가장 순환로 중에서 가장 긴 사이클을 찾아야 한다. 도시의 모든 정점은 알파벳 소문자 1자로 표시된다. 따라서 도시는 최대 26개의 정점까지 가질 수 있다. 우리가 완성해야 할 마라톤 코스는 다음의 성질을 만족해야 한다.
1) 출발점 vertex는 항상 스타디움이 위치한 ‘a’로 고정되어 있다.
2) 설계된 순환로는 선수가 헛갈리지 않도록 같은 지점(vertex)를 2회 이상 방문하지 않도록 구성되어야 한다. 즉 simple cycle이다.
3) 가장 긴 순환로가 하나 이상이면 더 많은 정점을 방문하는 순환로를 우선해야 한다.
4) 만일 거쳐 지나는 지점(vertex)의 개수도 같을 경우에는 거쳐가는 순서의 알파벨 순서가 사전식으로 더 빠른 것을 선호한다. 즉 $a \rightarrow b \rightarrow m...$이나 $a \rightarrow g \rightarrow d \rightarrow i...$ 의 길이가 동일하지만 알파벳 순서가 더 빠른 $a \rightarrow b \rightarrow m...$을 우선해야 한다.
5) 만일 위의 조건을 만족하는 순환로가 없을 경우도 있을 수 있다. 예를 들어 도로망이 Tree와 같다면 같은 지점을 2번 지나지 않고 되돌아오는 순환로는 존재하지 않는다. 이 같이 도로망의 모양에 따라서 순환로 자체가 존재하지 않을 경우도 있는데 이런 도시에서는 철인 마라톤 대회를 개최할 수 없다. 따라서 이 경우에는 “None”이라고 답을 해야 한다.
[입출력]
입력파일 iron.inp 의 첫 줄에는 정점(vertex)의 수 $N$과 edge의 수 $M$이 주어진다. 이어지는 M개의 각 줄에는 두 정점의 vertex $u, v$ 와 이 둘 간의 거리 $d_{u,v}$ 가 정수로 주어진다. 단 앞에 나오는 정점의 알파벳 순서가 뒤 정점보다 더 빠르다. 따라서 각 edge (u,v)는 입력 파일에 한번만 나타난다. 그리고 edge weight의 범위는 $1 \leq d_{u,v} \leq 20$이다. 그리고 edge 순서는 random하다. vertex 이름이 연속된 알파벳 순서는 아닐 수 있다. 즉 특정한 알파벳 vertex는 나타나지 않을 수도 있다.
출력 파일의 이름은 iron.out이다. 이 파일의 첫 줄에 우리가 구한 순환로의 길이, 즉 a에서 출발하여 다시 a로 돌아오는 가장 긴 순환 경로의 길이를 정수로 출력해야 한다. 그 다음 두번째 줄에는 a에서 출발하는 순환로의 정점(vertex)을 순서대로 공백을 넣어 출력한다. 시작은 항상 a이며 마지막에 돌아오는 출발점 a는 표시하지 않는다. 그림-1에 제시된 붉은색 점선 cycle이 그 답이다.
출력 파일의 이름은 iron.out이다. 이 파일의 첫 줄에 우리가 구한 순환로의 길이, 즉 a에서 출발하여 다시 a로 돌아오는 가장 긴 순환 경로의 길이를 정수로 출력해야 한다. 그 다음 두번째 줄에는 a에서 출발하는 순환로의 정점(vertex)을 순서대로 공백을 넣어 출력한다. 시작은 항상 a이며 마지막에 돌아오는 출발점 a는 표시하지 않는다. 그림-1에 제시된 붉은색 점선 cycle이 그 답이다.
[예제]
위 그림-1에 제시된 도로망의 경우가 아래 예제로 제시되어 있다.
[풀이]O($N!$)(backtracking)
이전 9번 마라톤 문제와 비슷한 문제다. 조건은 모두 동일하며, 기존 마라톤 문제가 edge의 sum이 42인 cycle을 찾는 것이었다면 이번 문제는 최대 크기의 cycle을 찾는 것이 차이점이다.
똑같이 가지치기를 해주면 되는데, tc가 이전 두 백트래킹 문제보다 더 빡쎄게 들어왔기도 하고, 만점자 중 속도가 빠른 10%에게 가산점을 주신다고 하셨으니 최대한 가지치기를 하여 속도를 줄이는게 관건이다.
내가 가지기치한 조건은 다음 조건들이다.
1. $a$에 연결된 vertex중 탐색 도중에 만난 vertex는 다시 $a$에서 탐색해 나갈 필요가 없다.
ex) $a \rightarrow b \rightarrow c \rightarrow a$와 $a \rightarrow c \rightarrow b \rightarrow a$는 같다.
따라서 $a$에서 시작해서 $a$에 인접한 vertex에 한번이라도 방문이 된 경우 $a$에서 다시 그 vertex로 나갈 필요가 없다.
2. 각 vertex에 연결된 간선들의 최대값을 구해놓고, (현재 경로 + 앞으로 남은 vertex들의 최대값의 합)이 현재 내가 구한 답 maxLen보다 낮으면 탐색할 필요 없이 가지치기하면 된다.
각 vertex에 연결된 간선들의 최대값의 합은 그 어떤 cycle의 cost보다 크다. 따라서 현재 위치에서 남은 vertex들의 최대값의 합을 더해도 maxLen보다 낮은 경우 더 이상 탐색할 가치가 없다.
3. 플로이드와샬을 이용하여 모든 vertex $i$에서 $j$로 이동가능한지 판별해놓고, 현재 지점에서 $a$로 이동이 불가능한 경우 가지치기한다. 4번 조건의 완전부분집합이다.
4. $a$와 연결된 vertex들과 나머지 vertex들의 이동 가능성을 check해둔다. visited배열과 (현재 vertex에서 갈 수 있는 $a$와 연결된 vertex)를 비교하여 모든 vertex가 visited에 들어가 있다면 $a$로의 도달가능성이 없어지는 것이므로 가지치기해준다.
위 4조건이 전부이고, 3번 조건은 논리적으로 4번조건에 완전부분집합이나 4번을 구현하는 과정에서 3번을 이용하는게 편하므로 그냥 3번조건도 같이 써주었다.
4번조건에서 visited배열과 (현재 vertex에서 갈 수 있는 $a$와 연결된 vertex)배열을 비교하는 과정을 그냥 배열로 구현하면 시간이 오래걸릴 것 같아서 long long type으로 비트마스킹해주었다.
지금 생각해보면 결국은 cycle에서 하나의 간선만 제거하면 spanningTree의 형태가 되므로 maximum spanning tree를 구한 뒤, 그냥 maximumEdge를 하나 더 해준 값으로 pruning해주면 훨씬 더 빨라졌을 것 같다.
처음엔 1번조건만 bound걸어주고 제출하니 100점이긴하나 10개 tc 시간이 18초가량이 나왔다.
그 이후 3번 조건을 걸어주었는데 시간은 큰 차이가 없었고, 4번조건을 배열로 구현하니 시간이 너무 오래걸려서 접었다.
여기에 적지않은 조건이 있는데, 4번의 완전부분집합인데다 개념도 비슷하다. 그 조건을 걸어주니 12초 가량으로 줄었으나, 순위권내에는 못 들었고, 노력대비 성적비중이 낮다고 판단하여 깔끔하게 접었다.
그러다 제출마감 4시간 전에 갑자기 오기가 생겨서 2번 조건을 걸어주고, 4번을 bitmask로 구현하여 걸어주니 5.2초에 안착했고, 아직 결과발표 전이나, 2등 일 것이라 예상된다.
2번 조건을 maximum spanning tree로 bound해주었으면 좀 더 빨라졌을 것 같은데 조금 아쉽다.
