방향그래프 순회 에러로그: indexOf의 함정

방향 그래프를 DFS로 순회하면서 특정 정점에 도달할 수 있는지에 대한 문제를 풀었다.

맨 처음에 작성한 코드는 다음과 같다.
-그래프를 입력받은 정점에서 순회하며 갈수있는 모든 정점을 배열에 저장한다.
-순회 방식은 DFS
-순회가 완료되면, 순회한 정점들이 배열에 저장되어 있을 건데, 만약에 입력받은 도착 지점이 없다면 그 도착지로 가는 경로가 없다는 뜻이다.

function getDirections2(matrix, from, to) {
  // TODO: 여기에 코드를 작성합니다.
  //방향이 있는 그래프이고, 순회한다. 
  //무방향 그래프는 순회하면 모든 정점을 다 볼 수 있음. 왜? 다 경로가 뚫려있으니까.
  //근데 방향있는 그래프의 경우에는 아무렇게나 순회를 못하기 때문에 순회하다가 중간에 끊길수있다,
  //내가 생각한건, 우선 from에서 순회를 하면서 방문한 지점을 배열에다가 순차적으로 담고,
  //그 결과 배열에 to 인자가 담겨있으면 참을, 
  //아니면 false를 리턴하도록 해야할거같다. 

  //순회 결과를 담을 배열을 선언한다, 
  let visited = [];

  //matrix를 순회한다. 뭘로 순회? DFS? BFS?
  //순회하면서 visited에 방문한 노드를 push한다. 
  (function traverse(start){
    //존재하지 않는 출발점일 경우,  리턴한다. 
    if(start >= matrix.length) return;

    //존재하는 출발점이라면 순회를 하며 visited에 방문한 정점을 push해야한다.
    visited.push(start);//방문 기록을 남긴다. 
    //만일 방문한 지점에 다른 경로로 갈 수 있는 길이 있니? 
    if(matrix[start].includes(1)){//있으면 한 번 더 반복 [0,0,0,1,0],[0,1,1,0,0];
      //그럼 그 배열 순회.
      for(let v = 0; v < matrix[start].length; v++){
        if(matrix[start][v]){//길이 있다면..
          if(visited.includes(v)){//이미 방문을 했던 지점이면 다시 돌아가지 않는다
            continue;
          }else{//방문을 하지 않았다면 그 점으로 가서 탐색을 시작한다.
            traverse(v); //여기도 호출스택이 쌓일건데 왜 여기는 잘만 되는것인지??
          }
        }
      }
    }

  })(from); //IIFE

  //순회를 종료하고, 도착지점에 도달할 수 있는지 여부를 리턴한다. 
  return visited.includes(to);
}

어제 복습을 하면서, 조금 다르게 풀어보려고 했다.
같은 DFS방식을 사용하되, 기존에 내가 노션에 정리해 둔 코드를 이용해서 풀어보기로 했다. 위의 코드는 일반적인 for문을 사용해서 조금 가독성이 떨어져 보였던 것 같다.
아무래도 문제 풀때는 정리해둔 공식을 써야 마음이 편해서 그런가..

새로 작성한 코드는 다음과 같았다.

function getDirections(matrix,start,end){
  //엣지 케이스: 만일 start나 end가 matix.length 이상이라면 false.
  if(start >= matrix.length || end >= matrix.length) return false;
  //인접 행렬의 모든 정점을 순회한다. 
  // //갈수있는 길이 없다면 ,방문기록에 남지 않을 것이다.
  // 그 배열이 end를 포함하는지 여부를 리턴하면 된다
  //방문 기록을 남기기
  const route = [];
  const visited = {};

  (function helper(node){
    visited[node] = true;
    route.push(node);

    matrix[node].forEach(neighbor => {
      if(neighbor === 1){ 
        let index = matrix[node].indexOf(neighbor); 
        if(!visited[index]){
          return helper(index); 
        }
      }
    })
  })(start)
  console.log(route);
  return route.includes(end);
}

통과가 안된 테스트 케이스는 다음과 같았다.

const matrix2 = [
  [0, 1, 0, 1],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 1, 0]
  ];

debugger;
console.log(getDirections(matrix2, 0, 2));

통과된 테스트 케이스의 경우, 모든 정점에 적어도 1이 다 포함이 되어 있었지만, 이 테스트 케이스의 경우에는 0에서 1로 가는 경로는 있었지만, 1에서 더 이상 갈 수 있는 경로가 없었다.(그림으로 그려보니, 통과한 케이스와는 다르게 트리처럼 그림이 그려졌다.)

아무튼 순회를 하면, 0,1,2,3 정점을 모두 순회해야 했는데, 순회 결과에는 [0,1]만 출력이 되었다. 즉, 첫번째 정점에서 1번 인덱스까지만 조회를 하고 종료가 되었다.
아무리 생각해도 이해가 안되었었는데, 문제는 indexOf의 역할을 내가 정확하게 인지를 못했다는 것이었다.
indexOf는 배열에서 특정 요소가 "처음으로" 나오는 인덱스를 반환하는데,
나는 모든 인덱스에 대해서 다 반환을 하는 것으로 착각을 했다.
맨 처음에 내가 작성한 코드를 보면, for문을 썼기 때문에 모든 인덱스를 정확하게 찾을 수 있었는데, forEach를 이용한 두번째 코드에서는 인덱스를 1까지밖에 조회를 못하기 때문에, 1번 정점의 3번 인덱스를 조회할 수 없었다.

그래서 indexOf를 사용하지 않기로 했고, 대신에 forEach함수에서 index인자를 사용하기로 했다. 이렇게 하면 정확한 인덱스를 가지고 올 수 있다.

neighbor, index이렇게 두개의 인자를 ()없이 그냥 썼더니, 아래 사진처럼, 에러가 떴다.
처음에는 neighbor를 담고 있는 배열이 비어있는게 원인인가 생각했는데,
화살표함수 부분에서 문법 에러가 있어서 그랬던거였다.

느낀점
괜히 호출 스택을 의심하며 디버깅을 해봤다.. 디버깅이 아직도 어렵다..
디버깅 할때 힘들어져서 멍하니 그냥 마우스클릭만 했는데, 한번한번 할때맏다 어디를 하고있는건지, 놓치지 않아야 할 텐데..

좋은 웹페이지 즐겨찾기