210416 TIL

자료구조에 대한 내용들이 너무 어렵다. 문제를 마주했을 때 아무리 해결 방법을 떠올려봐도 머리가 실타래처럼 꼬이기만 하고, 결국 실마리를 찾지 못한다. 오늘 민철님이 강의 중에 많이 풀어보다 보면 나중에는 문제를 보면 어떤 식으로 방법을 찾아가야 할지 보일거라고 했다. 그래서 그냥 풀리지 않던 문제들의 레퍼런스를 보고, 주석을 꼼꼼히 달며 이해한 후 레퍼런스를 보지 않고 스스로 작성해가는 연습을 해보려고 한다.

혹시 다음 기수 중에 이것을 보고 계신 분들이 있다면, 이 아래에는 레퍼런스 코드가 등장하니 보길 원하지 않으시면 나가는 것을 권해 드린다. 하지만 레퍼런스를 봐도 도저히 이해가 안된다면, 내가 코드 옆에 끄적여 놓은 주석들이라도 도움이 되었으면 좋겠다. (기본적으로 레퍼런스에도 자세하게 주석으로 설명이 달려 있다. 거기에 더 추가해서 작성해 보았다.)

인접행렬 길찾기

// 그래프 문제를 해결 할 때 queue를 사용한다는 아이디어
function getDirections(matrix, from, to) {

  // 1단계 - matrix와 같은 1차원 행렬을 생성해서 방문 여부를 체크한다.

  // queue를 간단하게 생성하고, 첫 시작점으로 from을 할당합니다.
  const queue = [from]; // 왜 인덱스를 할당을 하나 생각했는데, 배열안에 from을 넣는다는 뜻이었다.
  const enqueue = (n) => queue.push(n); //enqueue는 n을 인자로 받아 queue에 push한다. 
  const dequeue = (n) => queue.shift(); //dequeue는 인자가 필요 없고 queue를 shift한다. 그런데 queue는 [from]인데?? 
  // 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다. (matrix와 다른 또 다른 배열을 만들어 주는 것.)
  const isVisited = new Array(matrix.length).fill(false); // isVisited는 matrix의 길이만큼의 배열을 생성하고 인자를 모두 false로 채워준다.
  //let arr = new Array(4).fill(false) [false, false, false, false]
  // 첫 정점 방문 여부를 표시합니다.
  isVisited[from] = true // from은 첫 정점이다. 첫 줄을 true로 채워준다.

  // 2단계 - matrix의 정점들을 순회하면서 간선들을 확인한다. 확인한 후에는 isVisited를 true로 바꾸어준다.
  
  // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다. 
  while (queue.length > 0) { 
    // queue에서 정점을 하나 빼서 now에 할당합니다.
    const now = dequeue(); // queue니까 가장 앞에 있는 정점을 now에 할당
    // 목적지인지 검사하고, 목적지라면 true를 반환합니다.
    if (now === to) return true;
    // 해당 정점의 간선들을 확인합니다.
    for (let next = 0; next < matrix[now].length; next++) { // matrix[now]가 matrix행렬의 한 요소(배열)이다.
      // 만약, 간선이 있고 방문하지 않았다면
      if (matrix[now][next] === 1 && !isVisited[next]){ // 배열에 간선(1)이 있고, isVisited의 요소가 false이면
        // queue에 next를 넣습니다. (다음 정점으로 가기 위해)
        enqueue(next);
        // 해당 정점을 방문했다는 것을 표시합니다.
        isVisited[next] = true
      }
    } 
  }
  // 길이 없다면 false를 반환합니다.
  return false;
}

이 문제는 두개의 단계로 나누어서 생각해야 한다.
첫째, 필요한 변수와 메소드들을 할당하는 동시에 반복을 막아주는 배열을 생성할 것.
둘째, 행렬 안에 있는 요소를 from부터 검사해서 길이 있으면 true, 아니라면 false를 리턴.
그리고 그래프와 행렬이 등장하는 문제를 만났을 때, queue를 응용해야 하는 경우가 많다는 점도 잊지 말자.