BOJ 22526 - Fastest Route 링크
(2024.04.23 기준 G1)

문제

$1$번부터 $N$번까지의 $N$개의 스테이지가 있다. 스테이지를 한번씩 클리어해야 하며, 순서는 상관없다.
$i$번 스테이지를 클리어하면 $i$번 장비를 얻을 수 있다. 이 장비는 한 번 획득하면 계속 사용할 수 있다. 또한 각 스테이지를 클리어할 때 장비를 최대 하나만 사용할 수 있다.
각 스테이지마다 장비를 사용하지 않거나 혹은 임의의 장비 하나를 사용할 때의 클리어하는 시간이 주어질 때, 모든 스테이지를 클리어하는 최소 시간 출력

알고리즘

bit dp

풀이

현재 클리어한 모든 스테이지의 번호를 비트로 나타내보자. 이 비트가 같으면 진행해온 순서와 상관없이, 앞으로 남은 스테이지들을 클리어하는 최소 시간은 동일하다.

그러므로 현재 클리어한 스테이지의 상태를 비트로 나타내서 dp를 진행하면 된다.
각 상태마다, 어떤 스테이지를 클리어할 지는 비트가 켜지지 않은 번호를 찾으면 되고, 어떤 장비를 이용할 지는 비트가 켜진 번호를 찾으면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16, inf = 1e9;

int N, t[MAXN][MAXN + 1], dp[1 << MAXN];

// 현재 클리어한 스테이지를 비트로 나타낸다.
// 스테이지를 어떤 순서로 진행해왔어도, 클리어한 스테이지의 종류가 동일하면
// 앞으로의 남은 스테이지를 클리어하는 최소 시간은 동일하다.
// 이를 bit dp로 진행한다.
int dfs(int used){
    if (used == (1 << N) - 1) return 0; // 모든 스테이지를 클리어하면 종료
    if (dp[used] > 1) return dp[used]; // 현재 상태를 거쳐간 적이 있다면 저장된 값을 반환
    dp[used] = inf;
    for (int i = 0; i < N; i++) if (!(used & (1 << i))){ // 아직 클리어하지 않은 스테이지를 찾는다.
        int w = t[i][0]; // i번째 스테이지를 아무 장비없이 클리어하는 시간
        for (int j = 0; j < N; j++) if (used & (1 << j)) // 이미 클리어한 스테이지가 있다면
            w = min(w, t[i][j + 1]); // 거기서 얻은 장비를 이용하면 시간이 더 줄어드는지 확인
        dp[used] = min(dp[used], dfs(used | (1 << i)) + w); // i번째 스테이지를 클리어해본다.
    }
    return dp[used];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (cin >> N; N; cin >> N){
        for (int i = 0; i < N; i++) for (int j = 0; j <= N; j++) cin >> t[i][j];
        memset(dp, -1, sizeof(dp));
        cout << dfs(0) << '\n';
    }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import inf

# 현재 클리어한 스테이지를 비트로 나타낸다.
# 스테이지를 어떤 순서로 진행해왔어도, 클리어한 스테이지의 종류가 동일하면
# 앞으로의 남은 스테이지를 클리어하는 최소 시간은 동일하다.
# 이를 bit dp로 진행한다.
def dfs(used):
    if used == (1 << N) - 1: # 모든 스테이지를 클리어하면 종료
        return 0
    if dp[used] > -1: # 현재 상태를 거쳐간 적이 있다면 저장된 값을 반환
        return dp[used]
    dp[used] = inf
    for i in range(N):
        if not used & (1 << i): # 아직 클리어하지 않은 스테이지를 찾는다.
            w = t[i][0] # i번째 스테이지를 아무 장비없이 클리어하는 시간
            for j in range(N):
                if used & (1 << j): # 이미 클리어한 스테이지가 있다면
                    w = min(w, t[i][j + 1]) # 거기서 얻은 장비를 이용하면 시간이 더 줄어드는지 확인
            dp[used] = min(dp[used], dfs(used | (1 << i)) + w) # i번째 스테이지를 클리어해본다.
    return dp[used]

while True:
    N = int(input())
    if not N:
        break

    t = [list(map(int, input().split())) for _ in range(N)]
    dp = [-1] * (1 << N)
    print(dfs(0))