グラフィックと隣接マトリクス、隣接リスト2～4解答問題

グラフィックと隣接マトリクス
🙋‍♀️を選択します.
G(V vertax, E edge)
vertax(頂点):ノード、edge:ノードとノードを接続する幹線、エッジ.👉 頂点(V)と幹線(E)からなる集合
▼▼無方向図
各ノードが接続される形式(1番から2番まで、2番から1番まで)(双方向図と見なすことができる).
graph[a][b] =1, graph[b][a] =1

▼▼▼方向図
移動方向のあるグラフィック(双方向不可)
graph[a][b] =1

▼▼重み付け方向図
方向図と重み図
graph[a][b]=c(重み)ex)graph[1][2]=2

2.ナビゲーションパス(隣接行列:ノード数が少ない場合)
🙋‍♀️隣接行列
各ノードに整数型の配列インデックスを作成します.また,頂点間の接続状態は2次元配列の値で表され,配列[i][j]=1はインデックスiのノードとインデックスjのノードとの間に幹線が存在することを示し,それ以外は0である.

問題)方向図が与えられたとき、1番からN番までのすべてのパスの指数を出力するプログラムを作成します.下図の1番から5番までの指数は全部で6種類あります.

  function solution(n, arr) {
    let answer = 0;
    let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 인접행렬 만들 이차원 배열 n+1인 것 유의할 것! (1번 인덱스부터 사용하므로)
    let ch = Array.from({ length: n + 1 }, () => 0);
    let 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) {
            // DFS(i)를 기준으로 대칭적으로 추가하는 부분, 빼는 부분이 나뉜다!
            ch[i] = 1;
            path.push(i);
            DFS(i);
            ch[i] = 0; //백하는 지점
            path.pop(); // 백하는 지점
          }
        }
      }
    }
    path.push(1);
    ch[1] = 1; // 매우중요! 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)); //6

👉 D(1)から二重砲口.(ツリー化の練習を続ける)
｣DFS関数を実行する前に、ch[1]=1を行う必要があります(そうでなければ、戻り1のパスに追加されます).
3.ブラウズパス(DFS-隣接リスト:ノード数が多い場合に適用)
🙋‍♀️隣接リスト.
隣接行列を使用する場合,ノード数が多いほど時間的複雑度が大きくなる.(nの二乗)👉 この場合は隣接リストを使用します.
隣接リスト?各ノードに到達可能なノード番号を書きます.その後i=0~g[v].砲撃してlengthに当たった.ex)1では2、3、4を打つことができるので、0から3まで打つ.

隣接リストを使用して上記の質問に答える

  function solution(n, arr) {
    let answer = 0;
    let graph = Array.from(Array(n + 1), () => Array()); //n+1행과 빈열
    let ch = Array.from({ length: n + 1 }, () => 0);
    for ([a, b] of arr) {
      graph[a].push(b);
    }

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

4.迷宮を探る
7*7グリッド迷路から脱出する経路の指数を出力するプログラムを作成します.始点はメッシュの(1,1)座標,脱出終点は(7,7)座標である.仕切り板1は壁、0は通路です.格子板の移動は上下左右のみ移動します.

  function solution(board) {
    let answer = 0;
    let dx = [-1, 0, 1, 0];
    let dy = [0, 1, 0, -1];
    function DFS(x, y) {
      if (x === 6 && y === 6) answer++;
      else {
        for (let k = 0; k < 4; k++) {
          let nx = x + dx[k];
          let ny = y + dy[k];
          if (
            nx >= 0 &&
            nx <= 6 &&
            ny >= 0 &&
            ny <= 6 &&
            board[nx][ny] === 0
          ) {
            board[nx][ny] = 1; // 지나온길 다시 못돌아가게 1로 바꾸어줄 것!
            DFS(nx, ny);
            board[nx][ny] = 0; // 빽하는 지점
          }
        }
      }
    }

    board[0][0] = 1; // 꼭 체크 해주고 시작하기!
    DFS(0, 0);
    return answer;
  }
  let arr = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 1, 1],
    [1, 1, 0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0],
  ];

  console.log(solution(arr)); //8
  // dx 행 dy 열 헷갈리지 말기!
  
  

③③③③｣DFS関数を実行する前に、必ず始点を1に変更して、繰り返しても始点に戻らないようにします｣