경로 탐색 : 인접 행렬

내 풀이

function solution(n, arr) {
  let answer = 0;
  let check = Array(n + 1).fill(false);
  let connect = Array.from({ length: n + 1 }, () => []);

  // 바로 넣을 수 있도록 정렬
  arr = arr.sort((a, b) => {
    if (a[0] === b[0]) return a[1] - b[1];
    else return a[0] - b[0];
  });

  // 연결 상태 리스트
  for (let x of arr) {
    connect[x[0]].push(x[1]);
  }

  function DFS(node) {
    console.log(node, ':');
    console.log(check);
    if (node === n) {
      answer++;
      return;
    }
    for (let x of connect[node]) {
      if (!check[x]) {
        check[x] = true;
        DFS(x);
        check[x] = false;
      }
    }
  }
  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 [a, b] 로 넣어줄 수 있는줄 몰랐음 ㅠㅠ
• 생각해보니 굳이 정렬이 필요했을까? 하는 생각이 든다.

내 풀이 수정

function solution(n, arr) {
  let answer = 0;
  let check = Array(n + 1).fill(false);
  let connect = Array.from({ length: n + 1 }, () => []);

  // 연결 상태 리스트
  for (let [a, b] of arr) {
    connect[a].push(b);
  }

  function DFS(node) {
    if (node === n) {
      answer++;
      return;
    }
    for (let x of connect[node]) {
      if (!check[x]) {
        check[x] = true;
        DFS(x);
        check[x] = false;
      }
    }
  }
  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));

다시 인접 행렬로 수정했다 !

내 풀이 수정 2 (Solution 풀이)

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);

  path = [];

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

  function DFS(v) {
    if (v === n) {
      answer++;
      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);
  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));

이정도면 충분히 DFS 경로탐색에 대해 이해한 것 같다!