심야 배달 경로
골드 II의견: 0
한 택배 기사가 출발 도시 0번에서 시작하여 모든 도시를 정확히 한 번씩 방문한 뒤 다시 0번 도시로 돌아오려고 합니다. 도시 \(i\) 에서 도시 \(j\) 로 직접 가는 도로의 길이가 \(W_{ij}\) 로 주어질 때, 모든 도시를 한 번씩 방문하고 출발지로 돌아오는 가장 짧은 경로의 총 길이를 구하세요.
\(W_{ij}=0\) 인 경우 도시 \(i\) 에서 \(j\) 로 가는 직접 도로가 존재하지 않음을 의미하며 (대각선 \(W_{ii}=0\) 제외), 그 도로는 경로에 사용할 수 없습니다. 모든 도시를 도는 순회 경로가 존재하지 않으면 \(-1\) 을 출력합니다.
이 문제는 외판원 순회(TSP)로, \(N\) 이 작으므로 비트마스크 DP (\(O(2^N \cdot N^2)\)) 로 해결할 수 있습니다.
- \(2 \le N \le 15\)
- \(0 \le W_{ij} \le 1000\), \(W_{ii}=0\)
- \(W\) 는 대칭이 아닐 수 있습니다 (일방통행 도로 허용).
첫 줄에 도시의 수 \(N\) 이 주어집니다.
이어서 \(N\) 개의 줄에 걸쳐 \(N \times N\) 인접 행렬 \(W\) 가 주어집니다. \(i\) 번째 줄의 \(j\) 번째 수가 \(W_{ij}\) 입니다.
모든 도시를 한 번씩 방문하고 0번으로 돌아오는 최소 비용을 한 줄에 출력합니다. 불가능하면 \(-1\) 을 출력합니다.
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0800 → 1 → 3 → 2 → 0 순서로 돌면 \(10+25+30+15=80\) 으로 최소입니다.
3
0 5 9
5 0 7
9 7 021세 도시는 어느 순서로 돌아도 한 사이클의 길이가 \(5+7+9=21\) 로 동일합니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
심야 배달 경로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
심야 배달 경로