66. 경로탐색[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

 

풀이 

- 기존 문제에서 행렬이 아닌 벡터를 사용

- map[1].push_back(2) => 1번 인덱스에 2라는 노드가 생겨서 서로 연결 됨

- map[1].size()는 map[1]에 연결되어있는 노드의 수를 나타냄

- map[v][i] ex) map[1][2]이면 map[1]에 연결되어 있는 2라는 정점의 값이 됨

- ch[map[v][i]]가 0이면 해당 ch값을 1로 바꾼 후 DFS호출 => 호출 후 ch를 다시 1로 변경

 

#include<stdio.h>
#include<vector>
using namespace std;
int ch[30], cnt=0, n;
vector<int> map[30];
//66. 경로탐색(DFS 인접리스트 방법)
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;
}