[Algorithm]

🦕 인접 행렬 길찾기

🍀 문제 풀이

// function getDirections(matrix, from, to) {
//   // 방문했는지 확인하는 배열
//   const map = matrix.map(a => [...a].fill(0));  // 방문 여부

//   // 재귀를 돌리면서 길이 있는지 확인하는 함수
//   const canGetDirections = (matrix, from, to) => {
//     if(matrix[from][to]) return true;

//     // [0, 1, 0, 0]
//     // [0, 1, 0, 0] from = 0, to = 2 0부터 다른 노드까지 가는 길을 확인 후 그리고 그 길을 가본적이 있냐
//     for (let i = 0; i < matrix[from].length; i++) {
//       if(i === from || i === to) continue;

//       // from 이 바뀐다.
//       // 길이 있고, 방무한적이 없으면 거기로 가겠다.
//       if(matrix[from][i] && !map[from][i]) { //갈 수 있는 길이 있나
//       // 거기로 가면 여기서부터 다시 찾는다 목적지까지 갈 수 있는 길이 있냐
//         map[from][i] = 1;  // 방문처리를 해준거
//         if(canGetDirections(matrix, i, to)) return true;   // 갈 수 있는 길부터 다시 찾는다.
//       }
//     }
//     return false;

//   }
//   return canGetDirections(matrix, from, to);

// }


// const a = [
//    [0, 1, 0, 0],
//		[0, 0, 1, 0],
//		[0, 0, 0, 1],
//		[0, 1, 0, 0]
// ]

// a[0][2] === 1;
// 0 -> 1 -> 2 truen;
// 1 이냐 아니냐


function getDirections(matrix, from, to, visited = []) {
  // if(from === to) {
  //   return true
  // }
  if(matrix[from][to] === 1) return true;
    visited[from] = true; // 현재 노드를 방문했음을 표시

    // 간접적으로 이어진 경우를 찾아야함
    for (let i = 0; i < matrix[from].length; i++) {
      if(matrix[from][i] === 1 && !visited[i]) {
        if(getDirections(matrix, i, to, visited)) {
          return true
        }
      }
    }
    // 무한 루프를 어떻게 해결?
    return false;
}

🌲 회고