68. 최소비용 [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

 

풀이 

- 기존 인접리스트 형태와 비슷하나 pair를 사용해 2개의 값을 함께 연결한다

 

* pair

pair 선언: pair<int, int> 변수명

pair 만들기: make_pair(a, b) 

pair를 가지는 vector 만들기: vector<pair<int, int> > 벡터 이름 (>>는 쉬프트 연산자와 겹치므로 한칸 띄워줘야 함)

pair 값에 접근하기 : 첫번째 값 first, 두번째 값 second

 

- 연결된 정점과 비용은 다음과 같이 표현할 수 있다 EX(1, 2, 12) (1, 3, 6) / (2, 3, 2), (2, 5, 2)

1	0번 : (2, 12)	1번: (3, 6)
2	0번: (3, 2)	1번: (5, 2)

- 연결된 정점을 알아내고 싶다면 map[L][i].first / 연결된 정점의 비용을 알고 싶다면 map[L][i].second

- 주의할 점: 리스트 형태로 연결되어 있기 때문에 DFS 함수 안 for문이 0부터 map[L].size()보다 작을때까지 돈다

 

#include<stdio.h>

#include<vector>

using namespace std;

vector<pair<int, int> > map[30];

int ch[30];

int n, cost=2147000000;



//68. 최소비용(DFS: 가중치 방향그래프 인접리스트)

void DFS(int L, int sum){

    int i;

    if(L==n){

        if(cost>sum){

            cost=sum;

        }

    }else{

        for(i=0;i<map[L].size();i++){

            //리스트기 때문에 0~map[L].size()까지 돌아야 함

            if(ch[map[L][i].first]==0){

                ch[map[L][i].first]=1;

                DFS(map[L][i].first, sum+map[L][i].second);

                ch[map[L][i].first]=0;

            }

        }

    }

}



int main(){

    int i, m, a, b, c;

    scanf("%d %d", &n, &m);

    for(i=1;i<=m;i++){

        scanf("%d %d %d", &a, &b, &c);

        map[a].push_back(make_pair(b, c));

    }

    ch[1]=1;

    DFS(1,0);

    printf("%d\n", cost);

}