백준 23354 - 군탈체포조 (C++)

문제

• 문제 링크

  
   BOJ 23354 - 군탈체포조 
  

• 문제 요약

격자의 정보가 주어진다.
탈영병을 모두 잡고 부대로 복귀하는 최소 비용을 구해보자.

• 제한

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




$5 ≤ N ≤ 1,000

$1 ≤ N_{i,j} ≤ 1,000$

탈영병의 수는 $5$ 이하

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)
• 브루트포스 알고리즘(bruteforcing)

풀이

탈영병의 수만큼 다익스트라를 돌려 임의의 탈영병 위치에서 다른 탈영병 위치로의 최단 거리를 모두 구해주자.

그럼 답은

(탈영병을 최소로 순회하는 비용) + (첫번째 탈영병과 부대와의 거리) + (마지막 탈영병과 부대와의 거리)

이 된다. 탈영병의 수가 $5$로 굉장히 작아 모든 경우를 돌려보면 된다. (next_permutation)

이 문제에선 $k <= 5$였지만, $k <= 15$인 재밌는 문제가 여기 에 있으니 풀어보면 좋을 듯 하다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0 }, dx[]{ 0, 0, -1, 1 };
int n, c, M[1001][1001], D[7][7];
 
void f(int y, int x, int o)
{
    priority_queue<tuple<int, int, int>> Q;
    vector <vector <int>> W(1001, vector <int>(1001, (int)1e9));
    Q.push({ 0, y, x }); W[y][x] = D[o][o] = 0;
    while (Q.size())
    {
        auto [c, p, q](Q.top());
        c *= -1; Q.pop();
        if (W[p][q] >= c)
            for (int i{}; i < 4; i++)
            {
                y = p + dy[i], x = q + dx[i];
                if (y && x && y <= n && x <= n)
                    if (M[y][x] > 1000 && D[o][M[y][x] - 1000] > c) D[o][M[y][x] - 1000] = c, Q.push({ -c, y, x });
                    else if (!~M[y][x] && D[o][6] > c) D[o][6] = c, Q.push({ -c, y, x });
                    else if (int k(c + M[y][x]); M[y][x] > 0 && M[y][x] < 1001 && k < W[y][x]) W[y][x] = k, Q.push({ -k, y, x });
            }
    }
}
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fill(&D[0][0], &D[6][7], 1e9);
    cin >> n;
    for (int i(1); i <= n; i++)
        for (int j(1); j <= n; j++)
            if (cin >> M[i][j]; !M[i][j]) M[i][j] = 1000 + ++c;
    if (!c) cout << 0, exit(0);
}
void sv(int r = 1e9)
{
    for (int i(1); i <= n; i++)
        for (int j(1); j <= n; j++)
            if (M[i][j] > 1000)
                f(i, j, M[i][j] - 1000);
    vector <int> V(c + 1); iota(V.begin(), V.end(), 0);
    do
    {
        int s{};
        for (int i(2); i <= c; i++)
            s += D[V[i]][V[i - 1]];
        s += D[V[1]][6] + D[V.back()][6];
        r = min(r, s);
    } while (next_permutation(V.begin() + 1, V.end()));
    cout << r;
}
int main()
{
    in();
    sv();
}

comment

끝