경로탐색(인접행렬)

문제풀이 원리

코드

function solution(n, arr){  
        let gh = Array.from(Array(n+1), () => Array(n+1).fill(0));
        console.log(gh);
        let ch = Array.from({length:n+1}, ()=>0);
        console.log(ch);
        let answer = 0;
        for(let [a, b] of arr) gh[a][b] = 1;
        function DFS(v){
            if(v===n) answer++;
            else{
                for(let i=1; i<=n; i++) {
                    if(gh[v][i]===1 && ch[i]===0){
                        ch[i]=1;
                        DFS(i);
                        ch[i]=0;

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

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

1. graph를 통해 인접행렬이 어딘지 파악한다.

let arr=[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
let gh = Array.from(Array(n+1), () => Array(n+1).fill(0));
for(let [a, b] of arr) gh[a][b] = 1;

위처럼 arr인자들을 받아 연결되는 곳이 있으면 1로 표시해준다.

2. check를 통해 인자의 중복을 방지한다.

let ch = Array.from({length:n+1}, ()=>0);
//expected result: [0, 0, 0, 0, 0, 0]

DFS(1) -> DFS(2)를 실행하면 [1,2]로도 이어지지만 [2,1]로도 이어진다. 그러므로 갔던곳은 다시가지 못하게 해야한다.
ch에 갔던곳은 1로 표시해줌으로써 다시가지 못하게 한다.
(1이 시작점이므로 1은 항상 ch에 1로 표시해주어야 한다. -> ch[1]=1)