Funcia
Lv.4bitmaskdp

모든 도시를 한 번씩 도는 여행

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

도시 n개가 있고, cost[i][j]는 i번 도시에서 j번 도시로 가는 비용입니다. 가는 방향에 따라 비용이 다를 수 있습니다(cost[i][j] ≠ cost[j][i]일 수 있음). cost[i][i]는 0이며 쓰이지 않습니다.

0번 도시에서 출발해 나머지 모든 도시를 정확히 한 번씩 방문한 뒤 0번 도시로 돌아오는 여행의 최소 비용을 반환하세요.

입출력 예

costresult
[[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]35
[[0, 3], [7, 0]]10

입출력 예 설명

예 1 — 0 → 1 → 3 → 2 → 0의 비용은 10 + 10 + 9 + 6 = 35입니다.

예 2 — 도시가 두 개면 0 → 1 → 0 하나뿐입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(cost: int[][]) → int

제한 사항

  • 2≤n=2 \le n = cost.length ≤14\le 14, cost는 n×nn \times n
  • cost[i][i] = 0, i≠ji \ne j이면 1≤1 \le cost[i][j] ≤106\le 10^6

기대 복잡도

시간
O(2^N * N^2)
공간
O(2^N * N)

입출력 예

cost기대 출력
[[0,10,15,20],[5,0,9,10],[6,13,0,12],[8,8,9,0]]35
[[0,3],[7,0]]10

힌트

힌트

방문 순서를 모두 시도하면 (n−1)!(n-1)!가지라 n=14n = 14에서 6조 가지가 넘습니다.

그런데 남은 여행의 최소 비용은 "지금까지 어떤 도시들을 방문했고 지금 어디에 있는지"에만 달려 있고, 그 도시들을 어떤 순서로 방문했는지는 상관없습니다. 그래서 상태를 (방문한 도시 집합, 현재 도시)로 줄일 수 있고, 집합은 비트마스크로 표현합니다.

dp[mask][v] = "0번에서 출발해 mask의 도시들을 방문하고 지금 v에 있을 때까지의 최소 비용"

  • 시작: dp[1][0] = 0
  • 전이: mask에 없는 도시 w로 가면 dp[mask | (1 << w)][w] = min(…, dp[mask][v] + cost[v][w])
  • 답: min over v of dp[full][v] + cost[v][0]

상태 2n⋅n2^n \cdot n개, 전이 nn개라 O(2nn2)O(2^n n^2)이고, n=14n = 14에서 약 320만입니다.

복잡도 목표

모든 방문 순서(순열)를 시도하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness407판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.