17182 - 우주 탐사선

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

17182번: 우주 탐사선

생각해 보기

1. 방법은 여러가지가 있으나 가장 간단한 길을 생각해 보자.
2. 뒤로 돌아가도 상관 없다고 했으므로 플로이드 워셜을 이용해 가장 짧은 거리를 구하자.
3. 모든 방문 순서를 확인해 어떤 길이 가장 짧은지 확인하자.
4. 이전에 방문했던 방문 노드들이 같더라도 마지막에 방문하는 위치에 따라서 값이 달라질 수도 있다.
5. dp와 비트마스킹으로 최적을 구하려고 한다면, 단순히 1차원 chk[1<<11]로 하는게 아닌 2차원 chk[11][1<<11]로 해야 제대로 된 값을 구하게 된다.

코드

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

using namespace std;

int t[11][11];
bool chk[11];
int N,K,D;
int ans=987'654'321;

void input(){
    cin>>N>>K;

    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            cin>>D;
            t[i][j]=D;
        }
    }
}

void floyd(){    
    for(int k=0;k<N;++k){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                t[i][j] = min(t[i][j], t[i][k]+t[k][j]);
            }
        }
    }
}

void dfs(int node, int cnt, int ret){
    if(cnt == N){
        ans = min(ans, ret);
        return ;
    }

    for(int next=0; next<N; ++next){
        if(chk[next])
            continue;
        
        chk[next]=true;
        dfs(next, cnt+1, ret+t[node][next]);
        chk[next]=false;
    }
}

void solution(){

    floyd();
    chk[K]=true;
    dfs(K, 1, 0);

    cout<<ans<<'\n';
}

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

    input();
    solution();

    return 0;
}