[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

 

▷ 문제설명

그래프를 그려 문제를 해결해 보자. 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 

 

문제의 그래프는 정점이 단순히 연결되어 있을 뿐 아니라 방향을 가리키고 있다. 

예를 들어 1번 정점(vertex, 노드)은 2, 3, 4번 정점을 가리키고 있고, 1번과 2번 정점은 서로를 가리키고 있다.

 

graph[a][b]

이차원 배열을 만들고 a에서 b 정점으로 가는 간선(edge, 정점을 연결하는 선)이 있다면 1로 표시, 없다면 0으로 배열의 값을 채우면서 인접 행렬을 구현할 수 있다. 

 

▶︎ 내 답안

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

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

    function DFS(v) {
        if (v === n) {
            answer++;
        } else {
            for (let i = 1; i <= n; i++) {
                if (graph[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));

 

let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));

Array.from( ) 메서드를 통해 행과 열을 구현한다. 메서드의 첫번째 인자로는 n+1 길이의 배열이 들어가고, 두번째 인자로는 배열 각각에 값에 적용될 함수가 들어간다. 다시 말해 n+1 길이의 배열을 만들고, 배열 요소 각각에 n+1 길이의 배열을 집어 넣는다. (n이 아닌 n+1 길이의 배열을 생성하는 것은 인덱스 번호를 더 쉽게 활용하기 위함이다)

 

만들어진 이차원 배열의 모습은 다음과 같을 것이다. 

 

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

for of 문을 활용하여 이차원배열에 값을 채워보자.

 

이차원 배열을 완성했다면 DFS 함수를 통해 탐색을 시작한다. DFS로 순열을 구한 방법과 거의 유사하다.

 

ch[i] = 1;

ch는 'checked' 라는 의미로 배열에서 해당 인덱스의 숫자가 이미 사용되었는지 아닌지를 기록하는 역할을 한다. 특정 인덱스의 숫자가 사용되었다면 그 값을 1로 변경하여 사용된 숫자임을 마킹한다.

 

DFS(i) 함수 호출은 해당 인덱스의 숫자가 이미 선택된 적이 있는지를 if문으로 검사한 후 진행된다.

1로 마킹하는 것에서 끝나는 것이 아니라 해당 DFS(i)이 다 돌았다면 자녀 노드에서 부모 노드로 회귀할 때 다시 0으로 값을 초기화 해준다.

ch[i] = 0;

 

이때 주의해야 할 것은 문제에서 모든 경우의 수는 1번 정점에서 시작하므로 DFS 함수를 최초 호출하기 전에 미리 ch배열에 마킹을 해주어야 한다.

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

 

그래프를 통해 1번 정점에서 5번 정점으로 가는 경우의 수는 총 6가지가 된다. 최종 답으로 6이 출력된다.