Lv.4bitmaskdp
모든 도시를 한 번씩 도는 여행
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
도시 n개가 있고, cost[i][j]는 i번 도시에서 j번 도시로 가는 비용입니다. 가는 방향에 따라 비용이 다를 수 있습니다(cost[i][j] ≠ cost[j][i]일 수 있음).
cost[i][i]는 0이며 쓰이지 않습니다.
0번 도시에서 출발해 나머지 모든 도시를 정확히 한 번씩 방문한 뒤 0번 도시로 돌아오는 여행의 최소 비용을 반환하세요.
입출력 예
| cost | result |
|---|---|
[[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
제한 사항
-
cost.length,cost는 cost[i][i] = 0, 이면cost[i][j]
기대 복잡도
- 시간
- 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 |
힌트
힌트
방문 순서를 모두 시도하면 가지라 에서 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]
상태 개, 전이 개라 이고, 에서 약 320만입니다.
복잡도 목표
모든 방문 순서(순열)를 시도하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 7 | 판정만 |
| performance | 60 | 4 | 판정만 |