37.図形隣接行列の検索


グラフィック隣接行列の検索


鼻翼には草頭が止まっているような感じがします.どうしてもわからない!
リファレンスリファレンスリファレンスソースコードを参照してコードを記述し、デバッグを迂回していくつかの理解を行った.
首都コードを作成するときは、コードの役割を考慮し、コードのサイズを考慮してください.
ワンマン構成のコードですが、暗記した感じと言うべきでしょうか?
しかし、私はアルゴリズムをマスターしました.どうしてこんなに時間がかかるの...
结局今日はエピソード一つも理解できませんでした.休む.
もっと頑張ろうと思いますが、今日は反省の日です.
function getDirections(matrix, from, to) {
  // TODO: 여기에 코드를 작성합니다.
  // 순차적으로 탐색할수있도록 queue를 만들고, 그 첫번째 인자로 from을 넣는다.
  const queue = [from];
  const inqueue = (n) => queue.push(n);
  const dequeue = () => queue.shift();

  //해당 행을 탐색했는지 확인하기위한 배열을 만든다.
  const isCheckedRow = new Array(matrix.length).fill(false);

  // 첫 정점 확인여부를 표시, 방문하지 않았을 경우 queue 추가되어 확인진행을함
  // from은 queue에 들어있기 때문에 해당 행은 확인한것으로 취급
  isCheckedRow[from] = true;

  // 확인 로직 작성!
  // queue와 while은 친구!!
  // 확인할 행이 queue에 들어있기때문에 확인할 행이 빌때까지 확인반복
  while (queue.length > 0) {
    //queue의 0번째 인자를 꺼내고 확인용 행에 할당
    const currentRow = dequeue();
    //메트릭스의 행이 to과 같다면 간선이 연결된것
    if (currentRow === to) {
      return true;
    }
    // 현재행(정점)에 연결된(간선이있는) 정점들을 확인
    // 간선 유무 확인
    for (let i = 0; i < matrix[currentRow].length; i += 1) {
      // 간선이있고 연결된 행을 확인하지 않았다면 해당 행을 queue에 할당.
      if (matrix[currentRow][i] > 0 && !isCheckedRow[i]) {
        //if(간선이면1, 1이면 truthy && 확인안됬으면 true)
        // 확인 할 항목에 i를 추가 => 해당 행(matrix[i]행)을 확인목록에 추가
        inqueue(i);
        // 확인할 목록에 추가됫기때문에 해당행은 확인했음으로 처리
        isCheckedRow[i] = true;
      }
    }
  }
  return false;
}


console.log(
  getDirections(
    [
      [0, 1, 0, 1],
      [1, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0],
    ],
    1,
    3
  )
);
// > true