[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

인접행렬 방법으로 풀었던 문제이다.

최대 N이 커질 때 인접행렬을 사용할 경우 단점이 있다.

1. 메모리 낭비

2. 속도

최대 N 이 1,000,000 일 경우 인접행렬로 경로를 탐색할 경우

map[1000000][1000000] 크기의 이차원배열을 만들어야 한다.

이 경우 메모리를 차지하는 비용이 커진다.

그리고 각 정점과 연결된 정점을 찾을 때도 1000000 만큼 반복문을 돌며 탐색해야하므로

엄청난 속도 비용이 들 것이다..

이 때 인접리스트를 사용한다면 메모리, 속도면에서 굉장이 효율적인 결과를 볼 수 있을 것이다.

메모리 측면에서 vector<int> map[1000000] 의 일차원 벡터만 만들어도 되고,

속도 측면에서도 각 정점으로 연결된 정점의 정보를 담은 개수만큼만 반복문을 돌려도 된다.

#. 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

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

cs

인접 행렬로 구현했을 때 코드에서

line 42) map[s] 번째에 push_back 해주는 부분

line 18) map[v] 에 연결된 정점의 개수만큼 반복

line 20) map[v] 에는 정점 v와 연결된 정점만 저장되어있으므로 ch[map[v][i]] 가 방문을 했었는지만 확인해주면 된다.

line 21~ 는 동일하다.

#. 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

#include<stdio.h> #include<vector>   using namespace std;   int ch[30], cnt=0, n;         vector<int> map[30];   void DFS(int v){     int i;     if(v==n){         cnt++;     }     else{         for(i=0; i<map[v].size(); i++){             if(ch[map[v][i]]==0){                 ch[map[v][i]]=1;                 DFS(map[v][i]);                 ch[map[v][i]]=0;             }         }     } }      int main(){     int m, i, a, b;     scanf("%d %d", &n, &m);     for(i=1; i<=m; i++){         scanf("%d %d", &a, &b);         map[a].push_back(b);     }     ch[1]=1;     DFS(1);     printf("%d\n", cnt);     return 0; } Colored by Color Scripter

cs

ㅇ경로 출력 코드

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

#include<stdio.h> #include<vector>   using namespace std;       int ch[30], cnt=0, n, path[30]; vector<int> map[30];   void DFS(int v, int L){     int i, j;     if(v==n){         cnt++;         for(j=0; j<L; j++){             printf("%d ", path[j]);         }         puts("");     }     else{         for(i=0; i<map[v].size(); i++){             if(ch[map[v][i]]==0){                 ch[map[v][i]]=1;                 path[L]=map[v][i];                 DFS(map[v][i], L+1);                 ch[map[v][i]]=0;             }         }     } }                  int main(){     int m, i, j, a, b, c;     scanf("%d %d", &n, &m);     for(i=1; i<=m; i++){         scanf("%d %d", &a, &b);         map[a].push_back(b);     }     ch[1]=1;     path[0]=1;     DFS(1, 1);     printf("%d\n", cnt);     return 0; } Colored by Color Scripter

cs

#. Result

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

5 9

1 2 

1 3 

1 4 

2 1 

2 3 

2 5 

3 4 

4 2 

4 5

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

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

6

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