문제

문제 생각해보기

인접행렬에서는 graph를 만들어 0부터 모든숫자를 순회하며 1이 있나 살펴 았다.
graph

문제점

• 위의 문제는 접점이 5개이지만 접점이 많아지면 그만큼 많은 수를 선회해야한다.

문제 해결전략

• 접점의 수만큼 배열을 만들어 각 숫자에 접하는 숫자들을 배열에 넣는다.

graph = [ [], [ 2, 3, 4 ], [ 1, 3, 5 ], [ 4 ], [ 2, 5 ], [] ]

1에 접하는 수는 2,3,4
2에 접하는 수는 1,3,5
...

• dfs(v)에서 graph[v][i]를 돌며 재귀함수를 만들어준다.

코드

function solution(n, arr){  
        let gh = Array.from(Array(n+1), () => Array());               
        let ch = Array.from({length:n+1}, ()=>0);
        let answer = 0;
        for(let [a, b] of arr) gh[a].push(b);             
        function DFS(v){
            if(v===n){
                answer++;
                console.log(tmp);
            } 
            else{
                for(let i=0; i<gh[v].length; i++) {
                    if(ch[gh[v][i]]===0){
                        ch[gh[v][i]]=1; // dfs에 들어가기전에 v에 해당되는 숫자는 ch에 1로 바꿔준다.
                        DFS(gh[v][i]);
                        ch[gh[v][i]]=0; // dfs가 끝나면 다시 접근할 수 있게 0으로 바꿔준다.                  
                    }
                }
            }
        }
        ch[1]=1;
        DFS(1);
        return answer;
    }