우주탐사선

#include <iostream>  
#include <algorithm>  
#include <stack>  
#include <vector>  
#include <queue>  
  
using namespace std;  
  
/*  
 *시작행성으로 돌아올 필요 없음, 이미 방문한 행성도 중복해서 방문 가능  
 * [입]  
 * 행성수 N(10) 발사하는 행성위 츼치 K * 행성간 이동 시간(인접 행렬, 간선의 가중치 있음)  
 * * [출]  
 * 모든 행성을 탐사하기 위한 최소 시간  
 * * [조]  
 * 플로이드 워셜 알고리즘 사용 - 모든 정점 간 최단 거리  
 * 1. 플로이드 워셜로 정점간 최단 거리 구하기  
 * 2. 백트래킹을 이용해서 모든 경우의 수 (중복된 경우) 처리  
 *  *  
 */int INF = INT_MAX;  
int n, start;  
vector<vector<int>> dist;  
int min_cost = INF;  
  
void floyd_warshall(vector<vector<int>>& graph) {  
    for(int k=0; k<n ; k++) {  
        for(int start=0; start<n ;start++) {  
            for(int end =0; end<n; end++) {  
                if(graph[start][k] !=INF && graph[k][end] !=INF) {  
                    graph[start][end] = min(graph[start][end], graph[start][k] + graph[k][end]);  
                }  
            }  
        }  
    }  
}  
void dfs(int current, int visited_count, int total_cost, vector<bool>& visited) {  
    if(visited_count ==n) {  
        min_cost = min(min_cost, total_cost);  
        return;  
    }  
  
    for(int next=0; next<n; next++) {  
        if(!visited[next]) {  
            visited[next] = true;  
            dfs(next, visited_count+1, total_cost+ dist[current][next], visited);  
            visited[next] = false;  
        }  
    }  
  
}  
int main() {  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
  
    cin >> n >> start;  
    dist.assign(n, vector<int>(n));  
  
    for (int i = 0; i < n; i++) {  
        for (int k = 0; k < n; k++) {  
            cin >> dist[i][k];  
        }  
    }  
  
    floyd_warshall(dist);  
  
    vector<bool> visited(n,false);  
    visited[start] = true;  
    dfs(start ,1, 0, visited);  
  
    cout << min_cost;  
    return 0;  
}

벨만 포드 보다 플로이드 워셜

벨만포드는 모든 정점을 검사하지 않는다. 그냥 최단거리만 찾음
하지만 플로이드 워셜은 모든 경우의 수를 검사했을 때 최단 거리를 리턴한다.
즉 저기서 만든 graph는 모든 경우의 노드를 탐색했을 때최단 거리를 리턴한다는 것

void floyd_warshall(vector<vector<int>>& graph) {  
    for(int k=0; k<n ; k++) {  
        for(int start=0; start<n ;start++) {  
            for(int end =0; end<n; end++) {  
                if(graph[start][k] !=INF && graph[k][end] !=INF) {  
                    graph[start][end] = min(graph[start][end], graph[start][k] + graph[k][end]);  
                }  
            }  
        }  
    }  
}  

이건 플로이드 워셜 공식이다.
참고로 나는 인자를 start end k(중간에 거치느 노드)
이 순으로 외워서 사용하고 있다.

그래서 if문이 의미하게 되는건
start -> k로가는게 무한이 아니고 end ->k 로가는게 무한이 아니면(지나갈 수 있으면 지나칠 수 있는 노드라면)
start ->end 로 다이렉트로 가는 것과 start -> k -> end를 지나쳤을 때 두 비용을 정한다는 듯

참고로 나는 입력받을 때 dist가 0인 부분을(i ==j인 같은 부분 빼고 ㅎㅎ) 0인 부분은 INF로 처리해야하는데 까먹음 그리고 까먹었는데 정상수행이 되었다

중복이라는 말

문제를 보면 중복해서 간다는 말이 있다.

이미 방문한 행성도 중복해서 갈 수 있따는 말과
N의 범위를 보면 모든 경로를 탐색하라는 말을 알 수 있다.
N의 범위는 10밖에 안돼서 굉장히 작았다. 그럼 뭐다? 노가다로 알아낼 수있다. 노가다를 의미하는 건 뭐다? 백트래킹, 완전탐색 이라는 말

한 정점에서 특정 정점으로 갔을 때 최소 값을 플로이드 워셜로 구했으면 이제 중복해서 이동하는 모든 방법을 동원해 정답을 찾을 차례이다.

void dfs(int current, int visited_count, int total_cost, vector<bool>& visited) {  
    if(visited_count ==n) {  
        min_cost = min(min_cost, total_cost);  
        return;  
    }  
  
    for(int next=0; next<n; next++) {  
        if(!visited[next]) {  
            visited[next] = true;  
            dfs(next, visited_count+1, total_cost+ dist[current][next], visited);  
            visited[next] = false;  
        }  
    }  
  
}

현재 시작점, 몇 번째 방문인지, 비용은 얼마인가, 지나간곳?
을 인자로 받는다.

일단 지나간 수가 n과 같다면 모든 정점을 지나간 경우라면 가장 작은 값을 리턴한다.
이 경우는
백트래킹으로 이미 모든 경로를 탐색하고 가장 작은 값을 넣는 거라서 꼭
min(현재 젤 작은 값, 지금 백트래킹하면서 찾은 값) 이런식으로 찾아야한다

백트래킹을 통해 그래프의 모든 경로를 탐색하고 최소값을 찾으면 끝난다.

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL