Solution

Memo

  • 못풀었다! 🥲
  • 비트마스킹을 써서 쓰는 풀이가 있는걸 알았는데, 그걸 떠올리지 못하고 시간을 보내다가 지쳐서 다른 코드를 참고했다.
fn tsp(n: usize, grid: &[Vec<usize>]) -> usize {
    // dp[mask][i] = 지금 위치가 i 이며, mask로 표현된 도시를 방문했을때 최소 비용
    let mut dp = vec![vec![usize::MAX; n]; 1 << n];

    // 0001 0번 도시만 방문한 비용 0
    dp[1][0] = 0;

    // 모든 방문 경로에서
    for mask in 1..(1 << n) {
        // 해당 반복문의 시작 지점을 찾는다
        for i in 0..n {
            // mask & (1 << i) == 0 : 방문하지 않은 도시를 체크한다. 즉 방문하지 않은 도시에서 출발할 수 없다.
            // dp[mask][i] == usize::MAX 아직 도달하지 못한 경로
            if (mask & (1 << i)) == 0 || dp[mask][i] == usize::MAX {
                continue;
            }

            // 지금기준의 방문경로(mask)와 시작점(i) 다음 지점(j) 최소 비용을 구하고 memo
            for j in 0..n {
                if (mask & (1 << j)) != 0 || grid[i][j] == 0 {
                    continue;
                }

                let next_mask = mask | (1 << j);
                dp[next_mask][j] = dp[next_mask][j].min(dp[mask][i] + grid[i][j]);
            }
        }
    }

    let full_mask = (1 << n) - 1;
    let mut result = usize::MAX;

    for i in 1..n {
        if dp[full_mask][i] != usize::MAX && grid[i][0] > 0 {
            if let Some(cost) = dp[full_mask][i].checked_add(grid[i][0]) {
                result = result.min(cost);
            }
        }
    }

    result
}

solution을 풀어서 설명하면 다음과 같다

  • dp 정의

    • dp[비트로 표현한 지금까지의 경로][지금위치] = 비용
    • 즉 dp[0011][0], dp[0011][1] 은 각각
      • 0번, 1번 노드를 방문한 상태에서 지금 0번에 있는데 필요한 비용
      • 0번, 1번 노드를 방문한 상태에서 지금 1번에 있는데 필요한 비용

  • 기저 사례

    • dp[0001][0] = 0 : 0번시작 지금 0번에 있는 비용은 0

  • validation 1

    • i는 내가 지금 서있는 노드
    • 아래 처럼 아직 방문하지 않은 경로에 서있는경우, 아직 구해진 경로가 아닌경우는 패스
for i in 0..n {
	if (mask & (1 << i)) == 0 || dp[mask][i] == usize::MAX {
		continue;
	}
  • validation 2
    • j는 내가 지금 갈 노드
    • 아래처럼 j가 이미 방문한노드이거나, 비용이 0인경우(지금노드만 0이다)는 패스
for j in 0..n {
	if (mask & (1 << j)) != 0 || grid[i][j] == 0 {
		continue;
	}
  • dp값 계산
    • 이미 계산된 값과 지금 여기서 가는값중에 최소값
 dp[next_mask][j] = dp[next_mask][j].min(dp[mask][i] + grid[i][j]);
  • 정답구하기
    • dp[풀마스크된값 즉 모든 경로 방문한 경우에서][지금서있는위치] + 복귀비용
==== 테스트 케이스 : 4개 도시 ====
=== TSP 시작 ===
도시 수: 4
거리 grid:
[0, 10, 15, 20]
[5, 0, 9, 10]
[6, 13, 0, 12]
[8, 8, 9, 0]

초기 상태: dp[1][0] = 0 (0번 도시에서 시작)

=== mask = 1 (binary: 0001) ===
방문한 도시들: 0 
  현재 위치 0: 비용 = 0
    0→1: 현재비용(0) + 이동비용(10) = 10 (다음 mask: 0011)
      dp[0011][1] 업데이트: MAX → 10
        (방문도시: 0 1 )
    0→2: 현재비용(0) + 이동비용(15) = 15 (다음 mask: 0101)
      dp[0101][2] 업데이트: MAX → 15
        (방문도시: 0 2 )
    0→3: 현재비용(0) + 이동비용(20) = 20 (다음 mask: 1001)
      dp[1001][3] 업데이트: MAX → 20
        (방문도시: 0 3 )

=== mask = 2 (binary: 0010) ===
방문한 도시들: 1 
  (이 mask에서 유효한 상태 없음)

=== mask = 3 (binary: 0011) ===
방문한 도시들: 0 1 
  현재 위치 1: 비용 = 10
    1→2: 현재비용(10) + 이동비용(9) = 19 (다음 mask: 0111)
      dp[0111][2] 업데이트: MAX → 19
        (방문도시: 0 1 2 )
    1→3: 현재비용(10) + 이동비용(10) = 20 (다음 mask: 1011)
      dp[1011][3] 업데이트: MAX → 20
        (방문도시: 0 1 3 )

=== mask = 4 (binary: 0100) ===
방문한 도시들: 2 
  (이 mask에서 유효한 상태 없음)

=== mask = 5 (binary: 0101) ===
방문한 도시들: 0 2 
  현재 위치 2: 비용 = 15
    2→1: 현재비용(15) + 이동비용(13) = 28 (다음 mask: 0111)
      dp[0111][1] 업데이트: MAX → 28
        (방문도시: 0 1 2 )
    2→3: 현재비용(15) + 이동비용(12) = 27 (다음 mask: 1101)
      dp[1101][3] 업데이트: MAX → 27
        (방문도시: 0 2 3 )

=== mask = 6 (binary: 0110) ===
방문한 도시들: 1 2 
  (이 mask에서 유효한 상태 없음)

=== mask = 7 (binary: 0111) ===
방문한 도시들: 0 1 2 
  현재 위치 1: 비용 = 28
    1→3: 현재비용(28) + 이동비용(10) = 38 (다음 mask: 1111)
      dp[1111][3] 업데이트: MAX → 38
        (방문도시: 0 1 2 3 )
  현재 위치 2: 비용 = 19
    2→3: 현재비용(19) + 이동비용(12) = 31 (다음 mask: 1111)
      dp[1111][3] 업데이트: 38 → 31
        (방문도시: 0 1 2 3 )

=== mask = 8 (binary: 1000) ===
방문한 도시들: 3 
  (이 mask에서 유효한 상태 없음)

=== mask = 9 (binary: 1001) ===
방문한 도시들: 0 3 
  현재 위치 3: 비용 = 20
    3→1: 현재비용(20) + 이동비용(8) = 28 (다음 mask: 1011)
      dp[1011][1] 업데이트: MAX → 28
        (방문도시: 0 1 3 )
    3→2: 현재비용(20) + 이동비용(9) = 29 (다음 mask: 1101)
      dp[1101][2] 업데이트: MAX → 29
        (방문도시: 0 2 3 )

=== mask = 10 (binary: 1010) ===
방문한 도시들: 1 3 
  (이 mask에서 유효한 상태 없음)

=== mask = 11 (binary: 1011) ===
방문한 도시들: 0 1 3 
  현재 위치 1: 비용 = 28
    1→2: 현재비용(28) + 이동비용(9) = 37 (다음 mask: 1111)
      dp[1111][2] 업데이트: MAX → 37
        (방문도시: 0 1 2 3 )
  현재 위치 3: 비용 = 20
    3→2: 현재비용(20) + 이동비용(9) = 29 (다음 mask: 1111)
      dp[1111][2] 업데이트: 37 → 29
        (방문도시: 0 1 2 3 )

=== mask = 12 (binary: 1100) ===
방문한 도시들: 2 3 
  (이 mask에서 유효한 상태 없음)

=== mask = 13 (binary: 1101) ===
방문한 도시들: 0 2 3 
  현재 위치 2: 비용 = 29
    2→1: 현재비용(29) + 이동비용(13) = 42 (다음 mask: 1111)
      dp[1111][1] 업데이트: MAX → 42
        (방문도시: 0 1 2 3 )
  현재 위치 3: 비용 = 27
    3→1: 현재비용(27) + 이동비용(8) = 35 (다음 mask: 1111)
      dp[1111][1] 업데이트: 42 → 35
        (방문도시: 0 1 2 3 )

=== mask = 14 (binary: 1110) ===
방문한 도시들: 1 2 3 
  (이 mask에서 유효한 상태 없음)

=== mask = 15 (binary: 1111) ===
방문한 도시들: 0 1 2 3 
  현재 위치 1: 비용 = 35
  현재 위치 2: 비용 = 29
  현재 위치 3: 비용 = 31

=== 최종 결과 계산 ===
모든 도시 방문 완료 mask: 15 (binary: 1111)
도시 1에서 시작점으로: 35(방문비용) + 5(복귀비용) = 40
도시 2에서 시작점으로: 29(방문비용) + 6(복귀비용) = 35
도시 3에서 시작점으로: 31(방문비용) + 8(복귀비용) = 39
최종 결과: 35