백준 17182 우주 탐사선 C++

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

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)

---

출력

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

---

전에 풀었던 외판원 순회2와 비슷하면서 다른문제였다. 외판원 순회 2는 중복되서 방문하는 경우가 없었지만, 이 문제는 중복해서 이미 방문한 행성을 다시 방문해도 된다.

처음에 플로이드 - 와샬로 모든 경로에 대해 최단 경로를 구한다.

 

왜 플로이드 와샬을 사용해야 하는지에 대한 고민

->

 

예를 들어 시작을 2라고 해보자.

2에서 3으로 가는 경로는 배열[2][3]이다.

하지만, 2에서 3으로 가는 경로는 [2][3]뿐만이 아니다.

2에서 3으로 가는데 2->1을 거치고 1->3 으로 가는 경로(재방문 가능)가 최소의 경로일 수 도 있다.

그래서 플로이드 - 와샬을 사용해야 한다.

 

그후 백트래킹을 시작하는데, 나는 DFS를 그냥 처음 시작(0번쨰)부터 실행을 하였고,

K의 위치부터 출발을 하므로, DFS의 기저조건일 경우에 만약 배열의 처음부분이 K가아니면, 바로 리런을 하였고,

 

배열의 처음부분이 K일 떄, 값을 갱신하였는데

예를 들어서 N = 4이고 K가 2이면 1,2,3,4 .. 1,3,2,4 .....해서 2 1 3 4...

이런식으로 진행이 될텐데 배열의 처음 부분이 K인 2 1 3 4... 해서 처음이 무조건 K일때만 검사를 하였다.

다음 부분은 외판원 순회2와 비슷했다.

2 1 3 4, 2 1 4 3...해서 모든 K가 처음일 떄의 순열에 대해서 시간의 합을 구하고 최소 시간을 갱신해 주었다

(K가 처음일때만 !)

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int map[11][11];
bool visited[11];
int arr[11];
int n,k;
int min(int a,int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
 
int ans = 987654321;
 
void dfs(int start){
   if(start == n){
       if(arr[0] != k){
           return;
       }
       int sum = 0;
       for(int i = 0;i<n-1;i++){
           sum += map[arr[i]][arr[i+1]];
       }
       ans = min(ans,sum);
       return;
   }
    for(int i = 0;i<n;i++){
        if(visited[i] == false){
            visited[i] = true;
            arr[start] = i;
            dfs(start+1);
            visited[i] = false;
        }
    }
}
int main(void){
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> map[i][j];
        }
    }
    
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                map[i][j] = min(map[i][j],map[i][k] + map[k][j]);
            }
        }
    }
    
    dfs(0);

    cout << ans;
}