[BOJ] 5901 : Relocation

문제 링크

https://www.acmicpc.net/problem/5901

5901번: Relocation

다익스트라를 활용하는 문제

문제 해석

문제를 그대로 해석한게 아니라 해석해서 정리한 것이다.

농부 존은 그의 일과동안에 최단 경로로 다니기 위해서 농장의 위치를 옮기려고한다. 존이 이사를 계획하고 있는 마을은 총 N개의 마을이며 이 중에서 한 마을을 골라 거기에 농장을 지으려한다. N개의 마을 중 K개의 마을에는 마트가 있으며 존은 일과시간에 농장에서 출발해 K개의 마트를 돌고 다시 농장으로 돌아와야한다. 그리고 마트가 있는 마을은 땅값이 비싸기 때문에 마트가 있는 마을에는 이사를 가지 않는다. 즉, 선택지는 N-K 개의 마을이 있다. N-K개의 마을 중에서 가장 효율적으로 거리가 짧게 일과를 진행할 수 있도록 하는 마을을 찾아주자.

풀이

마켓이 5개 있다고 가정했을 때 임의의 농장 Farm에 대해서 존의 일과 진행 경로는 왼쪽 그림과 같을 것이다. 존이 가장 짧은 거리로 일과를 진행하기 위해서 각 노드 사이를 최단거리로 진행하면 된다. 여기서 마트를 방문하는 순서는 상관이 없다고 했다. 하지만 어떤 경로가 최적의 경로일지 모르니 모든 경우를 다 돌아봐야한다. next_permutation(순열)을 이용해서 마트를 방문하는 순서를 정해주었다. 즉 K팩토리얼 개의 경우를 다 돌아보았다. 마트가 최대 5개라고 했으므로 최대 5! = 120가지의 경우가 있을 것이다.

 

임의의 농장 Farm에 대해서 일과시간 최단경로를 계산하기 위해서는 각 마트 사이의 최단경로와 임의의 마트와 농장 사이의 거리를 알아야한다.

처음에는 dist라는 배열을 2차원으로 만들어서 dist[마트가 있는 마을의 번호][임의의 마을] 이렇게 마트에서 마을까지의 거리를 다익스트라로 계산해서 저장해두려고 했다. 하지만 이렇게 되면 예제문제는 잘 출력됐지만 10000 X 10000 개의 int 배열을 만들어야해서 메모리 초과가 났다.

그냥 마트의 인덱스를 0,1,2,3,4 로 정하고 dist[5][MAX_N]의 배열을 만들어주었다. 그리고 마트가 있는 마을의 번호는 Market[5] 배열을 선언해서 각 인덱스마다 마을의 번호를 저장해두었다.

다익스트라를 이용해서 마트와 마트사이의 거리, 임의의 마트와 임의의 마을 사이의 거리를 모두 구해놓은 다음 순열을 이용해서 마트방문 순서를 정하고 경로의 거리의 합의 최소를 찾아주면 된다. 임의의 농장 Farm은 K개의 마을을 제외한 모든 N-K개의 마을이 될 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 10000 + 5;
int Market[5];
int N, M, K; // 정점, 간선, 마트
vector<pair<int, int>> Edge[MAX_N];
int dist[5][MAX_N];
bool is_market[MAX_N];
int ans = INF;
 
void get_distance() {
    int order[5] = { 0,1,2,3,4 }; // 마트의 인덱스
    do {
        int cost = 0;
        for (int i = 0; i < K - 1; i++) {
            cost += dist[order[i]][Market[order[i + 1]]];
        }
        for (int i = 1; i <= N; i++) {
            if (!is_market[i]) // 출발점으로 가능하다면
                ans = min(ans, cost + dist[order[K-1]][i] + dist[order[0]][i]);
        }
    } while (next_permutation(order, order + K));
}
 
void dijkstra(int st) {
    Priority_queue pq;
    pq.push({ 0, Market[st]});
    while (!pq.empty()) {
        int now = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if (cost >= ans)
            break;
        if (dist[st][now] != INF)
            continue;
        if(now != Market[st])
            dist[st][now] = cost;
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            int acost = cost + Edge[now][i].second;
            if (dist[st][next] != INF)
                continue;
            pq.push({ acost, next });
        }
    }
}
void Init() {
    for (int i = 0; i <5; i++)
        for (int j = 0; j <= N; j++)
            dist[i][j] = INF;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    Init();
    for (int i = 0; i < K; i++) {
        int market; cin >> market;
        Market[i] = market;
        is_market[market] = true;
    }
    sort(Market, Market + K);
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        Edge[a].push_back({ b,w });
        Edge[b].push_back({ a,w });
    }
    for (int i = 0; i < K; i++)
        dijkstra(i);
    get_distance();
    cout << ans << "\n";
}