67. 최소비용 [DFS: 인접행렬]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5 8

1 2 12

1 3 6

1 4 10

2 3 2

2 5 2

3 4 3

4 2 2

4 5 5

 

출력예제 1

13

 

풀이 

- 일단 DFS로 탐색을 하려면 경로가 들어있는 map배열과 방문했는지 확인할 수 있는 ch 배열이 필요함

- 여기서는 정점(a)-정점(b) 관계와 비용 c를 map[a][b]=c로 표시한다

- 최소비용을 알기 위해서는 전역변수인 cost를 탐색하면서 작은 값이 나올때마다 바꾸어주어야 한다

- DFS(1, 0)부터 시작하는데 시작정점 1에서 sum=0인 상태로 탐색한다

- 정점이 1~n까지 있기 때문에 1에서 n까지 for문을 통해 (1) 연결되어있는지 (2) 방문했는지 확인해야한다

-> if(map[v][i]>0 && ch[i]==0)을 통해 위의 조건을 검사한다

- 방문하지 않았고 연결된 정점이라면 함수호출을 통해 연결된 해당 노드로 가주어야 한다

- > ch[i]=1 체크해주고 DFS(i, sum+map[v][i]) 연결된 i노드로 이동하면서 sum에 비용을 누적한다

- 최소비용이기 때문에 n까지 도달했을 시 누적해온 sum값이 cost값보다 작은지 확인한다

-> sum이 cost보다 작으면 cost=sum해준다

#include<stdio.h>
#include<vector>
using namespace std;
int n;
int map[30][30], cost=2147000000;
int ch[30];

//67. 최소비용(DFS: 인접행렬)
void DFS(int v, int sum){
    int i;
    if(v==n){
        if(sum<cost){
            cost=sum;
        }
    }else{
        for(i=1;i<=n;i++){
            if(map[v][i]>0 && ch[i]==0){
                ch[i]=1;
                DFS(i, sum+map[v][i]);
                ch[i]=0;
            }
        }
    }
}

int main(){
    int m, i, a, b, c;
    scanf("%d %d", &n, &m); //노드 간선
    for(i=1;i<=m;i++){
        scanf("%d %d %d", &a, &b, &c);
        map[a][b]=c;
    }
    ch[1]=1;
    DFS(1,0);
    printf("%d\n", cost);
}