백준 30975 - 약간 모자라지만 착한 친구야 (C++)

문제

• 문제 링크

  
   BOJ 30975 - 약간 모자라지만 착한 친구야 
  

• 문제 요약

경상국립대와 그 주변에 있는 동네 $N$개를 잇는 $M$개의 도로 정보가 주어진다.
동네별 $P_i$에 유의한 채, 경상국립대에서 시작해 모든 동네를 한 번씩 방문한 뒤 돌아오는 최소 시간을 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$1 ≤ P_i ≤ N ≤ 14$

$1 ≤ M ≤ 200$

$1 ≤ w_i ≤ 100$

시작 지점과 도착 지점이 모두 동일한 도로가 두 개 이상 존재할 수 있다.

알고리즘 분류

• 다이나믹 프로그래밍 (dp)
• 비트마스킹 (bitmask)
• 비트필드 위에서의 다이나믹 프로그래밍(dp_bitfield)
• 외판원 순회 문제 (tsp)

풀이

문제의 요구 사항과 제한을 보면 $tsp$ 냄새가 물씬 난다.
$N+1$번 정점까지 생각했을 때 정점의 수는 최대 $15$개가 될 수 있으므로, 방문 상태를 비트로 표현하는 $Bit$ $DP$로 문제를 풀 수 있다.

아래와 같이 상태를 정의해보자.

$dp[now][status]$ : 지금까지의 방문 상태가 $status$이고, 정점 $now$ 위에 서있을 때의 답.

기저 사례로, 모든 정점을 방문했다면 마지막으로 서있던 정점에서 $N+1$번 정점으로 돌아가는 비용을 반환하자.


$now$에서 $i$로 탐색이 들어가려면 아래의 조건을 충족해야 한다.

지금까지 $i$를 방문한 적이 없었는가?

$now$$→$$i$로 향하는 간선이 있는가?

$i$ == $p[i]$거나, $p[i]$번 정점을 방문하였는가?

상태가 $N*2^N$개, 각 상태를 계산하는 데에 $O(N)$의 시간이 걸리므로 문제를 총 $O(N^2*2^N)$에 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
 
int p[15], M[16][16], dp[15][1 << 15];
int n, m;
 
int f(int now, int status)
{
    if (status == (1 << (n + 1)) - 1)
        return M[now][n];
    int& cur(dp[now][status]);
    if (!~cur)
    {
        cur = inf;
        for (int i{}; i <= n; i++)
            if (!(status & (1 << i)) && M[now][i] < inf && (p[i] == i || status & (1 << p[i])))
                cur = min(cur, f(i, status | (1 << i)) + M[now][i]);
    }
    return cur;
}
int main()
{
    cin >> n >> m;
    for (int i{}; i < n; --p[i++])
        cin >> p[i];
 
    memset(M, inf, sizeof M);
    memset(dp, -1, sizeof dp);
 
    while (m--)
    {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        M[u][v] = min(M[u][v], w);
    }
 
    int ans(f(n, 1 << n));
    cout << (ans < inf ? ans : -1);
}

comment

끝