[알고리즘] 경로 탐색 - 인접 리스트

문제

방향그래프가 주어지면 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 가지입니다.

✏️ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

✏️ 출력설명
총 가지수를 출력한다.

✏️ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

✏️ 출력예제 1
6

---

풀이

function solution(n, arr){  
  const graph = Array.from({length:n+1},()=> Array());
  const visited = Array.from({length:n+1},()=>0);
  let answer = 0;
  for(let [a,b] of arr){
    graph[a].push(b);
  }
  function DFS(v){
    if(v === n){
      answer++;
      return;
    }
      for(let i = 0; i<graph[v].length;i++){
        if(visited[graph[v][i]]===0){
          visited[graph[v][i]] = 1;
          DFS(graph[v][i]);
          visited[graph[v][i]] = 0;
      }
    }

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

---

✏️ 문제 출처

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard