[Inflearn] 최소비용(DFS : 가중치 방향그래프 인접리스트 사용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

앞 문제와 똑같은데 이번에는 가중치 방향그래프를 인접리스트를 사용하여 풀어야 한다.

우선 가중치 방향그래프를 사용하기 위해서는 

vector<pair<int, int>> graph[3]; 를 사용해야 할 것이다.

벡터의 한 칸에 세 개의 요소 (출발 정점, 도착 정점, 가중치) 를 저장해야하기 때문에!

기존 코드에서 이 부분만 수정하면 될 것 같다. 

시간복잡도나 메모리 관리 측면에서 인접행렬보다 인접리스트가 훨씬 좋다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int n, m, rst = 2147000000; int ch[21]; vector<pair<int, int> > map[21];   void DFS(int v, int sum) {     int i;       if (v == n)     {         if (rst > sum)             rst = sum;     }     else     {         for (i = 0; i < map[v].size(); i++)         {             if (ch[map[v][i].first] == 0)             {                 ch[map[v][i].first] = 1;                 DFS(map[v][i].first, sum + map[v][i].second);                 ch[map[v][i].first] = 0;             }         }     } }   int main(void) {     freopen("input.txt", "rt", stdin);       int i, a, b, w;       scanf("%d %d", &n, &m);       for (i = 0; i < m; i++)     {         scanf("%d %d %d", &a, &b, &w);           map[a].push_back({ b, w });     }       ch[1] = 1;       DFS(1, 0);       printf("%d\n", rst);       return 0; } Colored by Color Scripter

cs

line 46) vector 의 한 칸에 도착 정점과 가중치를 저장해야하므로 pair 자료구조를 사용한다.

line 22) v 정점과 연결된 정점의 정보만 벡터에 저장되어있으므로 size() 만큼 반복문을 돌려준다.

line 24~29) 이전 코드와 동일한데 map[v][i].first 는 도착 정점을 의미하고

               map[v][i].second 는 가중치를 의미한다. 

               이 의미만 알면 충분히 풀어낼 수 있을 것이다.

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include<stdio.h> #include<vector> #include<algorithm> #define x first #define y second   using namespace std;       int ch[30], n, cost=2147000000; vector<pair<int, int> > map[30];   void DFS(int v, int sum){     int i;     if(v==n){         if(sum<cost) cost=sum;     }     else{         for(i=0; i<map[v].size(); i++){             if(ch[map[v][i].x]==0){                 ch[map[v][i].x]=1;                 DFS(map[v][i].x, sum+map[v][i].y);                 ch[map[v][i].x]=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].push_back(make_pair(b, c));     }     ch[1]=1;     DFS(1, 0);     printf("%d\n", cost);     return 0; } Colored by Color Scripter

cs

line 4~5) define 을 사용해서 first, second 대신 x, y 를 사용하였다. 코드가 나름 덜 복잡해질 수 있다.

line 33) pair 를 만들 때, {b, c} 도 가능하지만 make_pair(b, c) 도 가능하다.

인접리스트를 그림으로 그려보면 아래와 같다.

#. Result

  - Input --------------------------------------------------------

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

------------------------------------------------------------------

  - Output --------------------------------------------------------

13

------------------------------------------------------------------