[문제]
어떤 도시 NASUP에서 국제적인 마라톤 대회가 열린다. 우리는 이 대회를 위하여 42.195km의 마라톤 코스를 설계하는 과제를 맡았다. 도시의 도로망은 edge에 가중치가 있는 단순 그래프(simple graph) 형태이며, 두 교차로(vertex)를 지나는 도로(edge) 길이는 모두 정수(km)다. 우리는 이 도시에서 경기장에서 출발하여 다시 돌아오는 42km의 순환로를 만들어야 한다. 도시의 모든 정점은 알파벳 소문자 1자로 표시된다. 따라서 도시는 최대 26개의 정점까지 가질 수 있다. 우리가 완성해야 할 마라톤 코스는 다음의 성질을 만족해야 한다.
1) 출발점 vertex는 항상 스타디움이 위치한 a로 고정되어 있다.
2) 순환로는 선수가 헷갈리지 않도록 같은 장소를 2회 이상 방문하지 않도록 한다. (simple cycle)
3) 42km을 이루는 순환로가 하나 이상일 경우에는 가능하면 더 많은 정점을 방문하는 순환로를 더 우선한다. 예를 들면 아래의 예에서 8개의 점($a\rightarrow f\rightarrow m\rightarrow b\rightarrow c\rightarrow i\rightarrow d\rightarrow n\rightarrow a$)을 통과하는 외곽선 42km 순환로보다 파란색으로 표시한 내부 42km의 순환로( $a\rightarrow b\rightarrow m\rightarrow e\rightarrow k\rightarrow h\rightarrow i\rightarrow d\rightarrow g\rightarrow a$)가 더 많은 지점을 거치므로 이것이 더 선호된다.
4) 만약 두 경로의 거치는 지점의 수가 같을 때는 방문 지점의 알파벳 순서가 사전식으로 더 빠른 것을 선호한다. 위 경로를 시계방향으로 도는 $a\rightarrow b\rightarrow m\rightarrow \cdots$ 이나 반시계방향으로 도는 $a\rightarrow b\rightarrow m\rightarrow \cdots$ 모두 방문 지점의 수는 같으나 이 규칙에 따라 알파벳 순서가 더 빠른 $a\rightarrow b\rightarrow m\rightarrow \cdots$ 이 정답이 된다.
5) 어떤 경우 주어진 도로망에는 42km의 순환로가 존재하지 않을 경우도 있다. 이 경우에는 특별히 “None”이라고 답을 해야 한다.
[입출력]
입력파일 marathon.inp의 첫 줄에는 정점(vertex)의 수 과 edge의 수 이 주어진다. 이어지는 M개의 각 줄에는 두 정점의 vertex 와 이 둘 간의 거리 가 정수로 주어진다. 단, 앞에 나오는 정점의 알파벳 순서가 뒤 정점보다 더 빠르다. edge weight의 범위는 $1 \leq d_{u,v} \leq 20$ 이다. edge가 나타나는 순서는 random하다. vertex는 이름은 항상 연속된 알파벳 순서는 아닐 수 있다.(즉, N=5일때 사용되는 정점은 (a, b, c, d, e)가 아닌 (a, c, e ,f ,h)일 수도 있다.) 출력으로는 첫 줄에 42km 순환 경로 중에서 시작 점을 포함하여 거쳐가는 정점의 수를 출력한다(돌아오는 시작점은 경로에 넣지 않아도 된다.) 그다음 줄에는 a에서 출발하는 순환로 정점을 순서대로 공백을 하나씩 넣어 출력한다.
[예제]
|
marathon.inp |
marathon.out |
|
14 21 |
9
|
[풀이] O($N!$)
tsp문제에 모든 정점을 방문해야된다는 조건을 완화하고 경로합이 42인 경우만 고려하도록 제한한 문제이다. 완전탐색에 branch pruning으로 해결 가능하다.
생각할 필요 없이, 각 vetex에 연결되어있는 edge를 오름차순으로 정렬하고, edge를 탐색할 때 총 합이 42가 넘어가는 edge부터는 더 이상 고려할 가치가 없으므로 break 걸면 된다.
문제는, vertex가 26이고 완전 그래프인 상태에서 모든 edge가 1인경우에는 모든 경로합이 전부 26이므로 branch pruning이 되지 않는다. 즉, 온전히 $N!$이 걸리게 된다.
다행히도 그런 비정상적인 도시의 형태는 입력으로 들어오지 않고, 대략 vertex개수의 2배만큼 edge가 들어온다고 하셨으므로 pruning이 제대로 되겠다고 판단하여 제출했고, 통과했다.
dp문제에 비해 문제 난이도가 너무 낮아서 재미가 없었던 문제다.
