[인프런 섹션9] 경로탐색 인접행렬 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션] 경로탐색 인접행렬 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

 

✍️Idea Sketch

2021-06-30

1. 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수

2. DFS 종료조건

• v가 5일 때 종료

if (v === n) return;

3. DFS 로직

• DFS(v) v는 정점
• for() 반복문을 이용해 시작점이 v인 모든 배열 수행

for (let x of arr) {
  if (x[0] === v) {
    arr.push(v);
    DFS(x[1]);
    arr.pop();
  }
}

4. 1 -> 2 -> 4 -> 1 처럼 계속 순환하는 경우

• visited 배열 추가
• visited가 false인 경우에만 DFS 수행
• 방문하지 않은 노드만 방문

let visited = Array.from({ length: n + 1 }, () => false);

4. DFS 로직 수정

• DFS(v)를 수행하면 방문표시, res.push하기

function DFS(v) {
  visited[v] = true;
  res.push(v);
}

---

5. graph 만들기

let graph = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => 0));

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

 

✍️소스코드

2021-06-30

let n = 5;
let arr = [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
let visited = Array.from({ length: n + 1 }, () => false);

let res = [];
let cnt = 0;

function DFS(v) {
  visited[v] = true;
  res.push(v);

  if (v === n) {
    cnt++;
    return;
  }

  for (let x of arr) {
    if (v === x[0] && !visited[x[1]]) {
      DFS(x[1]);
      res.pop();
      visited[x[1]] = false;
    }
  }
}

DFS(1);
console.log(cnt);