[알고리즘 ]DFS 경로 탐색 경우의 수-인접행렬 with javascript

문제설명

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

예시) 1번정점에서 5번 정점까지 가는 경우의 수는

1->2->3->4->5

1->2->5

1->3->4->2->5

1->3->4->5

1->4->2->5

1->4->5

 

총 6가지이다.

 

입출력예시

 

총 가지수를 출력한다.

let arr = [[1,2],[1,3],[1,4],[2,1],[2,3],[2,5],[3,4],[4,2],[4,5]];

console.log("리턴값 :", countDfs(5,arr));

 

코드

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

    path.push(1);
    DFS(1);
    return count
}

 

function countDfs(n, arr) {
    //n = 정점 갯수 ,arr = 간선정보 
    let count = 0;
    //그래프가 2차원 배열 인접행렬 만들 배열, 행과 열 모두 n+1개 0번 인덱스는 비워놓고 할거기 때문이다.
    let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); 
    // vertex 노드를 방문했냐 안했냐를 체크하기 위해 ch만듬
    let ch = Array.from({
        length: n + 1
    }, () => 0);
    //콘솔을 위한 path
    let path = [];
    //arr의 하나씩 배열이 들어간다.
    for (let [a, b] of arr) {
        //이것이 방향그래프가 된다. 무방향 그래프는 graph[b][a]도해주면 된다.
        graph[a][b] = 1;
    }

    // DFS함수 만들기
    function DFS(vertex) {
        if (vertex === n) {
            count++
            console.log(path);
        } else {
            for (let i = 1; i <= n; i++) {
                //여기서 확인해줘야한다.vertex에서 i로 갈 수 있느냐
                //이미 방문했으면 안되기 때문에 ch[i] ===0이여야함
                if (graph[vertex][i] === 1 && ch[i] === 0) {
                    //방문 체크하고
                    ch[i] = 1
                    path.push(i)
                    //한 위치를 옮겼기 때문에 DFS에 i를 넣고 다시 돌린다. 
                    DFS(i);
                    //길을 찾고 나왔다면 뒤로 백해야하기 때문에 
                    //방문체크한 것을 지워줘야한다.
                    ch[i] = 0;
                    path.pop();
                }
            }
        }
    }

    path.push(1);
    //1부터 시작하기에 방문체크와 DFS에 1을 넣어 돌린다.
    ch[1] = 1  //위에 코드와 다른점은 이거 하나다. 1을 체크 안해줬기 때문에 2개의 경우가 더 나오게 된거다.
    DFS(1);
    //마지막에 카운트 리턴한다.
    return count
}

해석은 코드에서...

dfs는 방문체크가 중요한거같다.

길을 찾을때는 체크를 하고, 길을 찾거나 못찾더라도 들어갔다가 나오게 되면

방문 체크를 없애줘야 다른 길을 찾을 때 오류가 생기지 않는다.

 

 

손코딩도 해보았다. 못그렸지만ㅋㅋㅋㅋ

그래프 인접행렬 dfs 마스터하고싶다.