백준 20549번 - 인덕이의 고민

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

20549번: 인덕이의 고민

사실 비트마스킹문제를 풀고 싶어서 태그를 보고 문제를 풀었는데 비트마스킹을 몰라도 풀 수 있는 문제였습니다.

 

 

필요한 배경지식

• 다익스트라

 

문제 해결 방법

NxN 격자에서 오리가 이동할 수 있는 방법은 3가지가 있습니다.

체스룰에서 나이트, 비숍, 룩의 이동과 같은 이동방법인데

각각의 이동방법에 가중치가 존재합니다. 이것을 '오리가 받는 과부하의 양' 이라고 하여 각각 A,B,C로 입력을 받는데, 이것은 이동할 때 노드사이의 간선의 가중치가 다르다는 것을 의미하므로 최단거리를 구하기 위해서는 다익스트라 알고리즘을 사용해야 합니다.

 

한 노드에서 다른 노드까지의 간선의 개수를 한 위치에서 다른 위치로 이동할 수 있는 방법으로 나타내면 나이트의 이동은 8개, 룩이동 N+N-1개, 비숍이동은 최대 N+N-1개 이므로 대충 4N개라고 해도 다익스트라 한번의 시간복잡도는 O((N^2+N^2*4N)log(N^2)) = O(N^3 log(N^2)) 으로 구할 수 있습니다.

 

위에서 구한 결과는 한 시작점으로 부터 다른 위치까지의 최단거리입니다. 오리의 이동경로를 구할때, 위의 방법을 이용하여 오리와 먹이 그리고 모든 먹이와 먹이사이의 최단거리를 구할 수 있으므로 먹는 순서를 정하는 방법으로 완전탐색을 생각해 볼 수 있습니다. 먹이의 최대 개수가 4개이므로 다익스트라를 최대 5번 사용하고 DFS를 이용하여 먹이순서를 탐색해도 충분히 시간안에 들어올 수 있습니다.

 

 

전체 코드

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using tpi = tuple<int,int,int>;
const int INF = 0x3f3f3f3f;

int N,M;
int cost[3]{};
int sty, stx;
vector<pii> cord; // cordinate
int dist[5][50][50]{}; // dist[0]: 오리기준, dist[1~4]: 먹이기준
int ndy[8] = {-1,-2,-2,-1,1,2,2,1}; // night dy
int ndx[8] = {-2,-1,1,2,2,1,-1,-2};
int bdy[4] = {-1,-1,1,1}; // bishop dy
int bdx[4] = {-1,1,1,-1};
int rdy[4] = {-1,0,1,0}; // rook dy
int rdx[4] = {0,1,0,-1};

void dijk(int y, int x, int idx){
    priority_queue<tpi, vector<tpi>, greater<tpi>> pq;
    pq.push({0,y,x});
    dist[idx][y][x] = 0;

    while(!pq.empty()){
        int cd,cy,cx;
        tie(cd,cy,cx) = pq.top();
        pq.pop();

        if(cd > dist[idx][cy][cx]) continue;

        for(int i=0; i<8; i++){
            int nd = cd + cost[0];
            int ny = cy + ndy[i];
            int nx = cx + ndx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=N) continue;
            if(nd < dist[idx][ny][nx]) {
                pq.push({nd,ny,nx});
                dist[idx][ny][nx] = nd;
            }
        }

        for(int i=0; i<4; i++){
            for(int j=1; ; j++){
                int nd = cd + cost[1];
                int ny = cy + j*bdy[i];
                int nx = cx + j*bdx[i];
                if(ny<0 || nx<0 || ny>=N || nx>=N) break;
                if(nd < dist[idx][ny][nx]) {
                    pq.push({nd,ny,nx});
                    dist[idx][ny][nx] = nd;
                }
            }
        }

        for(int i=0; i<4; i++){
            for(int j=1; ; j++){
                int nd = cd + cost[2];
                int ny = cy + j*rdy[i];
                int nx = cx + j*rdx[i];
                if(ny<0 || nx<0 || ny>=N || nx>=N) break;
                if(nd < dist[idx][ny][nx]) {
                    pq.push({nd,ny,nx});
                    dist[idx][ny][nx] = nd;
                }
            }
        }
    }
}

int mind = INF; // min dist
bool vi[5]{};
void dfs(int dpt, int sum, int cidx){
    if(dpt == M) {
        mind = min(mind, sum);
        return;
    }

    for(int i=1; i<=M; i++){
        if(vi[i]) continue;
        vi[i] = true;
        dfs(dpt+1, sum + dist[cidx][cord[i].xx][cord[i].yy], i);
        vi[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dist,0x3f,sizeof(dist));
    cin>>N;
    for(int i=0; i<3; i++) cin>>cost[i];
    cin>>sty>>stx;
    cord.push_back({sty,stx});
    dijk(sty,stx,0);
    cin>>M;
    int y,x;
    for(int i=1; i<=M; i++){
        cin>>y>>x;
        cord.push_back({y,x});
        dijk(y,x,i);
    }

    dfs(0,0,0);
    cout<<mind;
}