외판원 순회 (정확해)
마스터의견: 0
\(N\)개의 도시가 있고, 두 도시 \(i\), \(j\) 사이를 직접 이동하는 거리 \(D_{ij}\)가 주어진다. 거리 행렬은 대칭이며(\(D_{ij} = D_{ji}\)), 대각 성분은 \(D_{ii} = 0\)이다.
한 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문하고 출발 도시로 돌아오는 순회(해밀턴 순환)를 생각하자. 이 순회의 길이는 연속한 두 도시 사이 거리의 총합이며, 마지막 도시에서 첫 도시로 돌아오는 거리까지 포함한다.
정수 \(B\)가 함께 주어진다. 총 길이가 \(B\) 이하인 순회를 하나 찾아 그 방문 순서를 출력하여라.
이 문제는 외판원 순회 판정 문제(TSP) 로, 잘 알려진 NP-완전 문제이다. 다항 시간 알고리즘은 알려져 있지 않으며, 만약 존재한다면 \(P = NP\)임을 증명하게 된다. 여기서 \(B\)는 이 인스턴스의 정확한 최적값으로 설정되어 있으므로, \(B\) 이하의 순회를 찾는다는 것은 곧 최적 순회를 찾는 것과 같다. 즉, 효율적으로 숨겨둔 지름길은 없다.
길이가 \(B\) 이하인 어떤 유효한 순회든 정답으로 인정된다.
\(4 \le N \le 200\)
\(0 \le D_{ij} \le 99\), \(D_{ij} = D_{ji}\), \(D_{ii} = 0\)
\(B\)는 해당 인스턴스의 최적 순회 길이와 같다.
이전 버전보다 \(N\)이 크게 늘었다 — \(2^N\) 비트마스크 DP(Held-Karp)는 더 이상 제한 시간·메모리 안에서 동작하지 않는다.
첫 줄에 도시의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 줄마다 \(N\)개의 정수가 주어지며, \(i\)번째 줄 \(j\)번째 수는 \(D_{ij}\)이다.
마지막 줄에 정수 \(B\)가 주어진다.
총 길이가 \(B\) 이하인 순회의 방문 순서를, 도시 번호(\(1\)부터 \(N\))의 순열로 한 줄에 공백으로 구분하여 출력한다. 출력한 순서대로 방문하고 마지막 도시에서 첫 도시로 돌아온다.
4
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
4
1 2 3 4네 도시가 정사각형 모양으로 놓여 있다. 인접한 변(길이 1)만 따라 한 바퀴 도는 순회 1-2-3-4가 길이 4로 최적이며, \(B=4\)이다.
6
0 1 1 99 99 99
1 0 99 99 1 1
1 99 0 1 99 1
99 99 1 0 1 1
99 1 99 1 0 1
99 1 1 1 1 0
6
1 2 5 6 4 3\(N=6\). 비용이 \(1\)인 길만 따라 모든 도시를 한 바퀴 도는 순회가 존재하며 그 길이는 \(6\)으로, 이것이 최적값 \(B\)이다. 비용 \(1\) 길을 벗어나면 어떤 순회든 더 길어진다.
riseoj 작성
출처 Original
평가 및 의견
외판원 순회 (정확해)
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
외판원 순회 (정확해)