[ 백준 ] 17182번 - 우주 탐사선 (C++)

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

17182번: 우주 탐사선

 

 

[ 문제풀이 ]

 

이 글을 일기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/24

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

 

1. 플로이드 와샬 알고리즘을 바탕으로 각각의 노드에서 노드까지의 최단 거리를 저장합니다.

 

2. 재귀 함수를 통해 모든 도시를 방문했을 때 최단 거리를 ans에 저장합니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

 

#include<iostream>
 
using namespace std;
 
int N, K;
int arr[10][10];
int dist[10][10];
int visited[10];
int ans = 987654321;
int hap;
 
void dfs(int cur, int level)
{
    if (level == N - 1) {
        ans = min(ans, hap);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] != 1) {
            visited[i] = 1;
            hap += dist[cur][i];
            dfs(i, level + 1);
            hap -= dist[cur][i];
            visited[i] = 0;
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            dist[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
 
    visited[K] = 1;
 
    dfs(K, 0);
 
    printf("%d", ans);
}