[Algorithm] 경로 탐색(그래프-인접리스트)

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

▶︎ 문제

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

 

 

▷ 입력 예제

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

 

▶︎ 출력 예제

6

 

▷ 문제설명

인접행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방법이다. 인접 행렬은 정점이 연결되어 있는지 확인하기 위해서 graph[a][b]의 요소만 확인할 수 있기 때문에 직관적이고 구현하기 쉽다는 장점이 있다. 

 

하지만 구현해야 하는 그래프의 정점(vertex, 노드)의 개수가 10억개라면 어떨까? 배열 하나의 요소를 확인하는데 O(1)의 시간복잡도를 가진다고 한다면 각각의 정점이 간선으로 이어져있는지 확인하기 위해서는 O(n)의 시간복잡도를 가지게 될 것이다. 10억 개의 정점이 있는 그래프를 탐색하려고 한다면 상당히 많은 시간이 걸릴 것을 예상할 수 있다. 

 

인접그래프는 인접행렬의 이러한 단점을 보완할 수 있다. 인접그래프는 각각의 정점에 대한 간선 정보를 리스트로 표현하는 방법이다. 쉽게 말해 간선(edge, 정점을 연결하는 선)으로 연결되어있는 정점의 정보를 저장하는 방법이다. 

문제 속 그래프를 인접그래프로 나타낸다면 다음과 같을 것이다.

 

 

(이때 정점의 순서는 상관없다. 1번 정점에 대한 정보가 2,3,4의 순서가 아닌 3,2,4의 순서로 저장되어도 상관없다)

인접행렬과 비교했을 때 for문으로 탐색해야하는 정보의 양이 훨씬 준 것을 확인할 수 있다. 간선의 숫자가 작을수록 인접그래프는 인접행렬보다 효율적으로 그래프를 탐색하는 방법이 된다.

코드로 인접리스트를 구현해보자.

 

▶︎ 내 답안

function solution(n, arr) {
    let answer = 0;
    let graph = Array.from(Array(n + 1), () => Array());
    let ch = Array.from({ length: n + 1 }, () => 0);

    arr.forEach(([a, b]) => {
        graph[a].push(b);
    });

    function DFS(v) {
        if (v === n) answer++;
        else {
            for (let i = 0; i < graph[v].length; i++) {
                let idx = graph[v][i];
                if (ch[idx] === 0) {
                    ch[idx] = 1;
                    DFS(idx);
                    ch[idx] = 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));

 

arr.forEach(([a, b]) => {
    graph[a].push(b);
});

이전 포스팅에서 사용한 for of 문 대신 forEach( ) 메서드를 통해 배열의 값을 채워보았다. 

만들어진 graph의 모습은 다음과 같을 것이다. 

 

인접리스트를 완성했다면 DFS 함수를 통해 각각의 정점에 관해 연결되어있는 배열을 탐색하기만 하면 된다. 

for (let i = 0; i < graph[v].length; i++) {
    ...
    }
}

for문은 배열 0부터 시작해 배열의 길이만큼만 탐색한다. 

 

let idx = graph[v][i];
if (ch[idx] === 0) {
    ch[idx] = 1;
    DFS(idx);
    ch[idx] = 0;
}

인접행렬과 마찬가지로 ch배열을 통해 해당 인덱스의 숫자가 이미 사용되었는지 아닌지를 기록한다. if문을 통해 ch배열에서 인덱스의 값이 0일 경우에만 DFS 함수를 호출한다. 

 

ch[1] = 1;
DFS(1);

문제에서 구하고자 하는 모든 경우의 수는 1번 정점을 반드시 지나므로 ch배열에 인덱스 1을 마킹하는 것을 잊지 말자.