[ALGORITHM] 백준 5852 - Island Travels

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

5852번: Island Travels

대강 해설

소들은 N(1 <= N <= 15)개의 섬 위에 있습니다. 섬은 R x C (1 <= R, C <= 50)의 크기 입니다. 섬의 위치는 X로 표시되어 있으며 좌우로 연결되어 있는 X는 동일한 섬입니다. 처음에 방문할 수 있는 섬은 아무곳이나 상관없으며 각 섬을 최소 한번씩 방문하면 됩니다. S는 수영을 하여 지나갈 수 있습니다. 최소한의 수영 횟수로 모든 섬을 방문하는 횟수를 구해주세요.

. : 깊은 물 (수영 불가 - 못 지나감)

X : 섬의 위치

S : 얇은 물 (수영 가능)

 

과정

1. 연결되어 있는 X를 하나의 섬으로 묶는다.
2. 각각의 섬들 사이의 거리를 구한다.(모든 섬울 방문하는 최소 거리를 구해야 되기 때문에)
3. 모든 섬을 시작점으로 한번씩 외판원 순회 알고리즘(Traveling Salesman Problem)을 이용하여 최소 거리를 구한다.

예제

5 4
XX.S
.S..
SXSS
S.SX
..SX

정답 : 3

3 5

XSXSX

..S..

..X..

정답 : 4

코드

#include<iostream>
#include<vector>
#include<queue>
#include<climits>

using namespace std;

typedef struct Data{
    int y,x,cost;
}d;

struct compare{
    bool operator()(d &a, d &b){
        return a.cost > b.cost;
    }
};

int my[4]={0,1,0,-1};
int mx[4]={1,0,-1,0};

int R,C;
char map[55][55];
int chk[1 << 17][20];
int visit_map[55][55];
int dist[20][20];
int cnt=1;

void input(){
    cin>>R>>C;

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin>>map[i][j];
        }
    }
}

void make_island(int y, int x, int num){
    map[y][x]=num;
    for(int m=0;m<4;m++){
        int ny=y+my[m];
        int nx=x+mx[m];

        if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]!='X')
            continue;
        
        make_island(ny,nx,num);
    }
}

void connect_island(){
    fill(&dist[1][0],&dist[19][20],INT_MAX);
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j]=='X'){
                make_island(i,j,cnt);
                cnt++;
            }
        }
    }
}

void make_map(int sy, int sx, int cow){
    fill(&visit_map[0][0],&visit_map[54][55],INT_MAX);
    priority_queue<d, vector<d>, compare> q;

    visit_map[sy][sx]=0;
    dist[cow][cow]=0;
    q.push({sy,sx,0});

    while(!q.empty()){
        int y = q.top().y;
        int x = q.top().x;
        int cost = q.top().cost;

        q.pop();

        if(visit_map[y][x] < cost)
            continue;

        if(map[y][x] < cnt)
            dist[cow][map[y][x]] = min(cost, dist[cow][map[y][x]]);

        for(int m=0;m<4;m++){
            int ny = y+my[m];
            int nx = x+mx[m];

            if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='.')
                continue;

            int ncost = cost + (map[ny][nx] == 'S');

            if(visit_map[ny][nx] > ncost){
                visit_map[ny][nx] = ncost;
                q.push({ny,nx,ncost});
            }
        }
    }
}

int tsp(int vst, int now){
    if(chk[vst][now] != 0 ) return chk[vst][now];
    if(vst == (1 << cnt) -1) return chk[vst][now] = 0;

    int ret = INT_MAX;
    for(int i=1;i<cnt;i++){
        if(vst & (1 << i)) continue;
        ret = min(ret, tsp((vst | (1 << i)), i) + dist[now][i]);
    }

    return chk[vst][now] = ret;
}

void solution(){
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j]<cnt && dist[map[i][j]][map[i][j]]!=0){
                make_map(i,j,map[i][j]);
            }
        }
    }


    cout<<tsp(1,0)<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    connect_island();
    solution();

    return 0;
}