백준 알고리즘 풀이 10971번 - 외판원 순회 2

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

10971번: 외판원 순회 2

---

- dfs 문제

 

알고리즘

---

1.  2차원 배열을 이용해서 N개의 노드와 엣지를 표현해준다.

2. dfs를 1부터 돌려주는데, count가 N이 된다면/ 더이상 방문할 노드가 없다면, 해당 dfs 종료.    

 

시간 복잡도

---

dfs의 시간복잡도인 O(V+E). 모든 노드가 다 이어져있는 경우 최대이므로 해당 상황을 가정한다면, O(2N)

 

소스코드

---

#include <iostream>
using namespace std;
int N;
int cost[11][11]={0,};
int isVisited[11]={0,};
int search(int now, int count){

    if(count==N){
        // cout<<"done"<<endl;
        // 현재 좌표에서 1번으로 가는 방법이 없다면, 최댓값을 넣어서 정답이 될수 없도록 한다.
        if(cost[now][1]==0){
            return 100000001;
        }
        else{
            // 다시 1로 돌아가는 방법이 있다면, 값을 넣어준다
            return cost[now][1];
        }
    }
    // 나올수 없는 최대한 큰 수로 한다. 10개의 노드와, 각 링크의 맥시멈이 1백만이므로 최대 1천만까지 나올수 있음.
    int ans = 987654321;
    for(int i=1;i<=N;i++){
        if(cost[now][i]!=0 && !isVisited[i]){
            isVisited[i] = true;
            // cout<<"여기 방문"<<i<<endl;
            // cout<<"걸리는 코스트 : "<<cost[now][i]<<endl;
            ans = min(ans,search(i, count+1)+cost[now][i]);
            isVisited[i]= false;
        }
    }
    return ans;
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            // i부터 j까지 가는 걸로.
            cin>>cost[i][j];
        }
    }
    isVisited[1] = 1;
    cout<<search(1,1);
    return 0;
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)