인접행렬 경로 탐색(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(5).fill(0));
    let check = Array.from({length : n+1},()=>0);

    for(let [a,b] of arr){
        graph[a][b] = 1;
    }

    function DFS(vertex){
        if(vertex === n){
            answer++;
        }
        else{
            for(let i = 1 ; i <= 5 ; i++){
                if(graph[vertex][i] === 1 && check[i] === 0){
                    check[i] = 1;
                    DFS(i)
                    check[i] = 0;
                }
            }

        }
    }
    check[1] = 1;
    DFS(1);
    return answer;
}

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

 

참고