백준 알고리즘 17182번 : 우주 탐사선

링크

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

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij ≤ 1000)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

예제 입력 및 출력

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

const int INF = int(1e9) + 1;

int n,k,dist[11][11],input[11][11],ans = INF;
bool vist[11] = {false,};

void reset(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

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

void dfs(int cur,int cost, int planet){
  if(ans < cost) return;
  if(planet == n){
    ans = min(ans, cost);
    return;
  }
  for(int i = 0; i < n; i++){
    if(vist[i]) continue;
    vist[i] = true;
    dfs(i, cost + dist[cur][i], planet + 1);
    vist[i] = false;
  }
}

int main() {
  fastio;
  cin >> n >> k;
  reset();
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> input[i][j];
      dist[i][j] = min(dist[i][j], input[i][j]);
    }
  }
  floyd();
  vist[k] = true;
  dfs(k, 0, 1);
  cout << ans;
  return 0;
}

Upsolving해야한다... 플로이드-와샬로 최단거리를 구하는 것은 알았지만 그걸 어떻게 처리할 지 접근법을 몰라서 틀렸던 문제..
결국 어흥님의 dfs소스코드를 참고했다 참고
k번에서 시작하므로 k번째에 방문 표시를 한 뒤에 dfs탐색을 시작한다.
cost는 현재 행성까지의 거리, cur은 현재 행성번호, planet은 탐색한 행성의 갯수
dfs를 이용해서 방문 순서를 정한뒤에 정해진 순서대로 방문하면서 모든 행성을 탐색하는 거리의 최솟값을 구한다.
순열을 사용해 방문 순서를 정해서 푸는 방식도 있다

next_permutation을 이용한 코드 추가 예정

next_permutation 코드 (성공 - 2021/09/07기준)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

const int INF = int(1e9) + 1;

int n,k,dist[11][11],ans = INF;

void reset(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

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

int main() {
  fastio;
  cin >> n >> k;
  reset();
  vi v(n);
  iota(all(v), 0);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int a; cin >> a;
      dist[i][j] = min(dist[i][j], a);
    }
  }
  floyd();
  do{
    int temp = k,cnt = 0;
    for(int i = 0; i < n; i++){
      cnt += dist[temp][v[i]];
      temp = v[i];
    }
    ans = min(ans, cnt);
  }while(next_permutation(all(v)));
  cout << ans;
  return 0;
}