64. 경로탐색 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5 9

1 2

1 3

1 4 

2 1

2 3

2 5

3 4

4 2

4 5

 

출력예제 1

6

 

풀이 

- v(정점)==n이 될때 종료지점, 이 때가 1에서 n까지 도착한 것이기 때문에 cnt를 증가 

- v==n이 아닐때는 각 정점에서 갈 수 있는 정점을 찾는다 

- 아직 가지 않았고, 간선이 연결되있는 정점을 찾는다 => ch[i]==0 && map[v][i] ==1

-  ch[i]에 1을 넣고 DFS(i) => 끝난 후에는 ch[i]를 0으로 초기화한다

#include <stdio.h>
#include <algorithm>
using namespace std;
int map[30][30], ch[30], cnt=0, n;
//64. 경로 탐색(DFS)

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 i, m, a, b;
    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);
}