인접 리스트 경로 탐색(DFS)

문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드)

 

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

12345

125 
13425
1345

1425

145

총 6 가지입니다.

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

▣ 출력설명
총 가지수를 출력한다.

 

▣ 입력예제 1

5 9

1 2

1 3

1 4

2 1  

2 3

2 5

3 4

4 2

4 5

 

▣ 출력예제 1

6

 

Tip

 

문제풀이

//정답보고 내가 다시 작성한 정답
function solution(n, arr){
    let answer = 0;
    let graph = Array.from(Array(n+1),()=>Array());
    let check = Array.from({length : n+1},()=>0);

    for(let [a,b] of arr){
        graph[a].push(b);
    }

    function DFS(vertex){
        if(vertex === 5){
            answer++;
        }
        else{
            for(let newVertex of graph[vertex]){
                if(check[newVertex] === 0){
                    check[newVertex] = 1;
                    DFS(newVertex);
                    check[newVertex] = 0;
                }
            }
        }
    }
    check[1] = 1;
    DFS(1)
    return answer;
}


let arr2=[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
console.log(solution(5, arr2));