[C++] DFS - 경로탐색(기초)

#include <iostream>

int map[21][21];
int N,M;
int cnt = 0;
int ch[30];
// 이게 없으면 cycle생김
//방문한 노드 체크를 해야함

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; // 일 끝나면 0으로 돌려놓음
            }
        }
    }
}

int main() {
    int a,b;
    int i;
    scanf("%d %d",&N,&M);
    
    for(i = 1; i <= M; i++){
        scanf("%d %d",&a,&b);
        map[a][b] = 1;
    }
    ch[1] = 1;//1에서 시작 체크
    
    DFS(1);
    
    printf("%d",cnt);
    return 0;
}

• 일반적으로 DFS 재귀함수의 매개변수가 Level로 따졌으나, 경로 탐색에서는 출발 노드(자기 자신)가 매개변수가될 수 있다.
• 그리고 방문한 노드는 다시 방문하지 않도록 꼭 체크해주어야 한다.
• 본인의 일이 끝났으면 체크를 꼭 풀어주어야 한다.
• 1번 노드에서 갈 수 있는 노드를 for문을 통해 인접행렬을 검사한다. 결과는 2 ,3 ,4이다. 2번 노드를 갔다면
• 2번 노드가 자기 자신이 되고 갈 수 있는 곳은 1, 5이다. 1은 체크되어있으므로 5로 가서 정답이 된다.
• 일이 끝났으면 STACK FRAME의 복귀주소로 가면서 체크배열을 다시 풀어준다.

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