[baekjoon] 23354

군탈체포조 

문제

군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다.

어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 주어졌는데, 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비를 최대한 아끼면서 탈영병을 모두 잡으려고 한다.

지도는 N×N 크기의 격자로 표현된다. 지도 위에는 부대와 탈영병들의 위치가 주어지며 부대나 탈영병이 없는 나머지 칸에는 모두 톨게이트가 존재한다. 

각 톨게이트에는 내야 하는 통행료가 정해져 있고 톨게이트가 있는 칸을 방문하기 위해서는 반드시 통행료를 지불해야 한다. 또한 같은 칸을 여러 번 방문해도 매번 통행료를 내야 한다.

호열이는 부대에서 출발해 탈영병을 모두 잡은 후 복귀해야하며, 중간에 부대를 들려도 상관없다. 단, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있고 지도에 표시된 곳 이외의 공간에는 갈 수 없다.

아무것도 하기 싫은 호열이를 위해 부대에서 출발해 탈영병을 모두 잡은 후 부대로 복귀하는데 드는 최소 비용을 대신 구해주자.

입력

첫째 줄에 격자의 크기 N이 주어진다. (5≤ N ≤1,000)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. −1은 부대, 0은 탈영병, 1이상의 정수는 톨게이트의 통행료를 의미하며 모든 통행료는 1,000 이하의 정수이다.

단, 입력에서 부대는 1개만 주어지며 탈영병의 수는 5명 이하로 주어진다.

탈영병이 존재하지 않을 수도 있다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

5
1 3 2 0 9
2 0 4 4 3
5 3 -1 1 1
3 7 2 0 1
1 2 3 5 0

예제 출력

16

 

 

풀이

처음에 단순히 생각해서 군부대(처음 시작 지점)로부터 다익스트라를 돌리고 가장 가까운 탈영병의 위치로 가서 다시 다익스트라를 돌리고... 마지막 탈영병에서 군부대로 복귀를 생각했지만 시작지점을 기준으로 한 다익스트라 결과랑 탈영병들의 위치로 한 다익스트라 결과가 별개이기 때문에 안 됐다.

 

그러다 어차피 모든 탈영병의 위치를 들려 야하기 때문에 군부대, 탈영병마다 다익스트라를 돌린 결과를 가지고 군부대로부터 출발해서 어느 탈영병부터 들릴지 모든 경우를 계산해 보면 되겠다고 생각했다.

 

탈영병이 3명이라 하면 아래 경우를 모두 계산해서 최소거리를 구한다.

 

군부대 ➜ 1번  +  1번 ➜ 2번 + 2번 ➜ 3번 + 3번 ➜ 군부대

군부대 ➜ 1번  +  1번 ➜ 3번 + 3번 ➜ 2번 + 2번 ➜ 군부대

군부대 ➜ 2번  +  2번 ➜ 1번 + 1번 ➜ 3번 + 3번 ➜ 군부대

군부대 ➜ 2번  +  2번 ➜ 3번 + 3번 ➜ 1번 + 1번 ➜ 군부대

군부대 ➜ 3번  +  3번 ➜ 2번 + 2번 ➜ 2번 + 1번 ➜ 군부대

군부대 ➜ 3번  +  3번 ➜ 3번 + 3번 ➜ 3번 + 1번 ➜ 군부대

 

입력값을 예전에 쓰던 다익스트라코드에 맞춰서 node와 result를 구성했더니 메모리 초과가 발생했다.. OTL

//메모리 초과............
int main(){
    int n = 1000;

    vector<pair<int, int>> *node;
    node = new vector<pair<int ,int>>[n*n];
    result = new int*[n*n];
    result = new int[n*n];

    //노드 구성
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            int nodeNumber = n * y + x;
            for(int i = 0; i < 4; i++){
                int nextX = directionX[i] + x;
                int nextY = directionY[i] + y;
                int nextNodeNumber = n * nextY + nextX;
                
                if(isOut(nextX, nextY))continue;
                else {
                    node[nodeNumber].push_back(make_pair(board[nextY][nextX], nextNodeNumber));     
                }
            }
        }
    }
}

그래서 result는 필요한 만큼만 할당받고 다익스트라를 돌릴 때는 node 구성을 따로 하지 않고 2차원 배열로 입력받은 것을 이용했다.

 

#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> deserterNodeNumber; //  탈영병 노드 번호
int militaryNodeNumber;
int **result;
int **board;
int INF = 0x7FFFFFFF;
int directionX[4] = {1, -1, 0, 0};
int directionY[4] = {0, 0, 1, -1};

int n;

bool isOut(int x, int y){
    if(x >= n || x < 0 || y >= n || y < 0)return true;
    else return false;
}

void dijkstra(int ptr){
    int start;
    if(ptr == 0) start = militaryNodeNumber;
    else start = deserterNodeNumber[ptr-1];
    for(int i = 0; i < n*n; i++)result[ptr][i] = INF;
    result[ptr][start] = 0;
    priority_queue<pair<int, int>> pq; // dis , node
    pq.push(make_pair(0, start));
    
    while(!pq.empty())
    {
        int currentNode = pq.top().second;
        int currentDistance = -pq.top().first;
        pq.pop();
        
        if(currentDistance > result[ptr][currentNode])continue;

        for(int i = 0; i < 4; i++){
            int nextX = currentNode % n + directionX[i];
            int nextY = currentNode / n + directionY[i];

            if(isOut(nextX, nextY))continue;

            int next = nextY * n + nextX; // board[y][x]
            int nextDistance = board[nextY][nextX] + currentDistance;

            if(nextDistance < result[ptr][next]){
                result[ptr][next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
}
void solve(){
    int size = deserterNodeNumber.size();
    if(size == 0){
        cout << 0;
        return;
    }

    result = new int*[size+1];
    for(int i = 0; i < size+1; i++){
        result[i] = new int[n*n];
        dijkstra(i);
    }
    
    int minimum = INF;
    vector<int> permutation;
    for(int i = 0; i < size; i++)permutation.push_back(i);

    do{
        int distance = 0;
        int startNode = permutation[0];

        //시작 지점(군 부대) -> N 탈영병 -> N + 1 탈영병 .... -> 군 부대
        distance += result[0][deserterNodeNumber[startNode]];
        for(int i = 0; i < size; i++){
            if(i == size - 1){
                distance += result[permutation[size-1] + 1][militaryNodeNumber];
                break;
            }
            int nextNode = deserterNodeNumber[permutation[i+1]];
            distance += result[permutation[i] + 1][nextNode];
        }

        
        if(minimum > distance){
            minimum = distance;
        }
    }while(next_permutation(permutation.begin(), permutation.end()));

    cout << minimum;
}



int main(){
    cin >> n;
    board = new int *[n];

    //입력 받기
    for(int y = 0; y < n; y++){
        board[y] = new int[n];
        for(int x = 0; x < n; x++){
            cin >> board[y][x];
            if(board[y][x] == 0)deserterNodeNumber.push_back(y * n + x);
            else if(board[y][x] == -1){
                militaryNodeNumber = y * n + x;
                board[y][x] = 0;
            }
        }
    }
    solve();
}

이후에도 군부대 들렸다가 가도 되는 줄 몰라서 몇 시간 동안 왜 안 되는 거지... 삽질했다....

※문제를 잘 읽자※