[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

우선 이차원 배열에 인접 행렬 정보를 저장한다.

그 다음이 핵심인데,

완전 탐색을 해야하므로 재귀함수를 사용해야 할 것이다.

D(1)부터 노드를 지날 수 있는지 없는지를 확인한 후 

이어진 간선을 통해 경로를 만들어나아가야 할 것 같다.

대략적인 코드를 먼저 짜보자.

void D(int lv)

if(lv == n)    // 종료 조건을 먼저 설정하고

{               // D(5) 까지 왔다는 것은 1번 정점에서 5번정점으로 도착했다는 것이다.

if(!ch[n])    // 5번 노드를 방문하지 않않다면 return

return;

int pos = 1;

for(i = 2; i <= n; i++)

if(i == 0) 

continue;

if(a[ch[pos]][ch[i] == 0)    // 두 정점이 연결되어있지 않다면

break;

pos++;

if(i == n)

cnt++;

    

return;

}

else

{

ch[lv + 1] = 1;

D(lv + 1);    // 다음 번호의 정점을 방문할 경우

ch[lv + 1] = 0;

D(lv + 1);    // 다음 번호의 정점을 방문하지 않을 경우

}

위 코드는 처음으로 짠 코드이다..

완전 오답에 형편없다..ㅋㅋㅋㅋ

결국 강사님의 힌트를 얻고 다시 생각해보았다.

알고나면 너무 허무한데 아직까지도 재귀함수가 복잡하게 느껴지는 것 같다..

우선 1번 정점 부터 5번 정점까지 연결된 구간을 확인하면서 길을 만들어야한다.

과정을 간단하게 짜보면

1 - 2 - 3 - 4 - 5

       - 5

    3 - 4 - 2 - 5

           - 5

...

순차적으로 탐색하기 위해서는 1부터 n 까지의 반복문이 필요할 듯 하다.

if(v == n)

cnt++;

else

{

for(i = 1; i<=n; i++)

{

if(map[v][i] == 1 && ch[i] == 0)    // 해당 정점(v)과 탐색 정점(i)이 연결되어있고, 

    아직 방문하지 않은 정점이라면

ch[i] = 1;    // 탐색 정점을 방문 처리를 해주고

DFS(i);    // 다음 정점으로 탐색을 시작한다.

ch[i] = 0;    // 탐색이 끝나고 방문 여부 체크를 해제해준다.

  (체크를 해제하지 않으면 다른 탐색 경로에서 방문한 정점 인식)

} 

}

알고보면 전혀 복잡하지 않은 코드인데,

왜 항상 복잡하게 생각하지ㅠㅠ

분발 분발!!

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

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int n, m, map[21][21], ch[21], cnt = 0;   void DFS(int v) {     int i;       if (v == n)         cnt++;     else     {         for (i = 1; i <= n; i++)         {             if (map[v][i] == 1 && ch[i] == 0)             {                 ch[i] = 1;                 DFS(i);                 ch[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][e] = 1;     }       ch[1] = 1;     DFS(1);       printf("%d\n", cnt);       return 0; } Colored by Color Scripter

cs

#. Other code

 
#include<stdio.h>    
 
int map[30][30], ch[30], cnt=0, n;
 
void DFS(int v){
    int i;
    if(v==n){
        cnt++;
    }
    else{
        for(i=1; i<=n; i++){
            if(map[v][i]==1 && ch[i]==0){
                ch[i]=1;
                DFS(i);
                ch[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][b]=1;
    }
 
    ch[1]=1;
    DFS(1);
    printf("%d\n", cnt);
    return 0;
}
 

DFS 고수가 되기 위해 귀찮지만 스택을 그려보며 과정을 다시 한 번 이해해보자!

인접 행렬은 아래와 같고,

	1	2	3	4	5
1		1	1	1
2	1		1		1
3				1
4		1			1
5

먼저 1번 정점부터 탐색을 시작한다.

정점 1과 연결된 정점을 찾기 위해 1 ~ n 까지 확인

1	2	3	4	5
1

D(1), i = 2, line22

정점 1은 정점 2와 연결되어있으므로 방문을 해보자.

1	2	3	4	5
1	1

D(2), i = 3, line22

D(1), i = 2, line22

정점 2는 정점 3과 연결되어있다. 마찬가지로 ch 배열에 체크 후 방문해보자.

정점 1은 이미 방문하였으므로 방문하지 않은 정점을 방문한다.

1	2	3	4	5
1	1	1

D(3), i = 4, line22

D(2), i = 3, line22

D(1), i = 2, line22

정점 3은 정점 4와 연결되어있다. 마찬가지로 ch 배열에 체크 후 방문해보자.

정점 2는 이미 방문하였으므로 패스

1	2	3	4	5
1	1	1	1

D(4), i =5, line22

D(3), i = 4, line22

D(2), i = 3, line22

D(1), i = 2, line22

정점4는 정점5와 연결되어있으므로 체크 후 방문

1	2	3	4	5
1	1	1	1	1

D(5)

D(4), i =5, line22

D(3), i = 4, line22

D(2), i = 3, line22

D(1), i = 2, line22

if(v == n) 조건에 의해 cnt++ 를 해주고 D(5) 함수는 종료된다.

방문된 정점은 1 2 3 4 5 이다.

1	2	3	4	5
1	1	1	1	1

D(4), i =5, line22

D(3), i = 4, line22

D(2), i = 3, line22

D(1), i = 2, line22

종료 후 체크 배열에서 i번 정점의 방문을 해제하고

D(4) 함수는 i가 n까지 다 돌았으므로 종료된다.

1	2	3	4	5
1	1	1	1

D(3), i = 4, line22

D(2), i = 3, line22

D(1), i = 2, line22

마찬가지로 i번 정점 방문을 해제하고

D(3) 함수는 i가 4까지 돌았지만 정점 3은 정점 5와 연결되어있지 않으므로

반복문이 종료되고 D(3) 함수도 종료된다.

1	2	3	4	5
1	1	1

D(2), i = 3, line22

D(1), i = 2, line22

D(2) 함수는 line 23 을 수행하고(i정점 방문 해제) 반복문을 마저 돈다.

정점 2는 정점 5와 연결되어있으므로 정점 5를 방문해보자.

1	2	3	4	5
1	1			1

D(5)

D(2), i = 5, line22

D(1), i = 2, line22

if(v == n) 조건에 의해 cnt++ 를 해주고 D(5) 함수는 종료된다.

방문된 정점은 1 2 5 이다.

다음도 마찬가지로 line 23 동작을 수행하고,

D(2) 함수는 반복문도 다 돌어갔으니 함수가 종료된다.

1	2	3	4	5
1	1

D(1), i = 2, line22

D(1) 함수는 다시 line23 번 동작을 수행하고(i정점 방문 해제)

다시 반복문을 돌리면, 3번 정점과 연결된다.

1	2	3	4	5
1

D(3), i = 4, line 22

D(1), i = 3, line22

...

안 풀릴 땐 스택을 쌓아가며 재귀함수와 놀아보자..

뭔가 대략적인 코딩으로 그려보려고 하다보니 복잡하게 되는 것 같다..

ㅇ경로 출력 코드

#include<stdio.h>    
 
int map[30][30], ch[30], cnt=0, n, path[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=1; i<=n; i++){
            if(map[v][i]==1 && ch[i]==0){
                ch[i]=1;
                path[L]=i;
                DFS(i, L+1);
                ch[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][b]=1;
    }
 
    ch[1]=1;
    path[0]=1;
    DFS(1, 1);
    printf("%d\n", cnt);
    return 0;
}
 

#. Result

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

5 9

1 2 

1 3

1 4 

2 1 

2 3 

2 5 

3 4 

4 2 

4 5

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

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

6

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