백준 25478 - Marinada (C++)

문제

• 문제 링크

  
   BOJ 25478 - Marinada 
  

• 문제 요약

$N * M$ 크기의 맵이 주어진다.
$U$에서 목표 지역을 모두 거친 뒤 $I$로 이동하는 최소 이동 거리를 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, M ≤ 1,000$

$1 ≤ K ≤ 16$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 너비 우선 탐색(bfs)
• 다이나믹 프로그래밍(dp)
• 비트마스킹(bitmask)
• 비트필드를 이용한 다이나믹 프로그래밍(dp_bitfield)
• 외판원 순회 문제(traveling salesman problem)

풀이

   구현량이 적은 편은 아니지만, 그리 어려운 구현은 없는 문제이다.
결국 구하라는 것은 목표 지점을 모두 순회하는 최소 순회를 찾는 것이고 $1 ≤ K ≤ 16$ 이므로 tsp 문제라 바라볼 수 있다.

이에 따라 차근차근 다음을 구현하자.

모든 $N$ 지점에 대해 bfs를 수행하여 $U$, $I$로 이동하는 거리와 다른 $N$ 지점까지의 거리를 모두 구하자.

$Dist(p, q)$를 $p$ 지점에서 $q$지점으로 이동하는 최소 비용이라고 하자.

그럼 결국 $1 ≤ K ≤ 16$ 인 $N_i$에 대해 $min(tsp$ _ $start(N_i)$ $+$ $Dist(N_i, U))$의 값을 찾는 문제가 된다.

각 순회에서 $N$인 지점을 모두 방문했을 땐 $I$로 이동하는 일만 남았으니 $Dist(last_x, I)$의 값을 반환하도록 구성하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0 }, dx[]{ 0, 0, -1, 1 };
int dp[16][1 << 16], D[16][1001][1001];
vector <pair<int, int>> V;
int n, m, k, r(2e9), i, j;
int p1, q1, p2, q2;
char M[1001][1001];
 
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp); memset(D, -1, sizeof D);
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> M[i][j];
            if (M[i][j] == 'N') V.push_back({ i, j });
            if (M[i][j] == 'U') p1 = i, q1 = j;
            if (M[i][j] == 'I') p2 = i, q2 = j;
        }
}
void f1(int p)
{
    queue <pair<int, int>> Q;
    Q.push({ i, j }); D[p][i][j] = 0;
    while (Q.size())
    {
        auto [a, b](Q.front()); Q.pop();
        for (int i{}; i < 4; i++)
        {
            int y(a + dy[i]), x(b + dx[i]);
            if (y && x && y <= n && x <= m && M[y][x] ^ '#' && !~D[p][y][x])
                D[p][y][x] = D[p][a][b] + 1, Q.push({ y, x });
        }
    }
}
int f2(int p, int q)
{
    if (q == (1 << k) - 1) return D[p][p2][q2];
    int& t(dp[p][q]), i{};
    if (!~t)
        for (t = 2e9; i < k; i++)
            if (!(q & (1 << i)))
                t = min(t, f2(i, q | (1 << i)) + D[p][V[i].first][V[i].second]);
    return t;
}
void sv()
{
    for (k = 0, i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (M[i][j] == 'N')
                f1(k++);
    for (i = 0; i < k; i++)
        r = min(r, f2(i, 1 << i) + D[i][p1][q1]);
    cout << r;
}
int main()
{
    in();
    sv();
}

comment

끝