[Graph] 인접 행렬 길찾기 : 깊이우선탐색(DFS)

필요한것 : isVisited 체크리스트, 재귀! **진짜 중요한것은 재귀안에 체크리스트가 포함되어 확인되어야한다. 변화된값을 가지고 들어가야됨.

 

 

필요없는것 : while,que <= bfs때 쓴것은 필요가없어요~

 

겹치는것 : isVisited만들기, for문과 for문안의 If조건 /  차이점  if안의 : 내용 if 만족되면 bfs는 que에 올려서 while문에서 돌게끔,dfs는 If문이 만족되면 재귀가 돌게끔.  

 

1. 초기 isVisited 값을 파라미터에 넣어준다.

 

isVisited=new Array(matrix.length).fill(false)

 

function getDirections(matrix,from,to)까지만있던것을 애초에 넣어서 바꿔버림

function getDirections(matrix, from, to , isVisited= new Array(matrix.length).fill(false))

 

2. isVisited 만들었으니 채우자

 

isVisited[from] = true;

 

3. while은 필요없고 while에서 그다음에있던 것? 조건! 끝나는 조건!

if(from == to) return true;

 

4. for 문돌리기 : bfs에서 분석한것 그대로 

 

for(let i=0; i<matrix[from].length;i++){

if(maatrix[from][i]===1 &&isVisited[i]===false){

 **이부분이 중요 let dfs = getDriections(matrix,i,to,isVisited)

if(dfs) {return true} 길이 존재한다면 true를 리턴해야 합니다 

만약 dfs면 <= 길이존재한다는 의미. true를 넣어줄수도 있고. if에 들어갓는지 확인도가능. 길이존재하지않으면 if(matrix[from][i])fh 로 안들어가고 걍 돌다가 for문이 끝남. 그러면 false로 나옴

}

}

 

function getDirections(matrix, from, to , isVisited= new Array(matrix.length).fill(false)) {
  // TODO: 여기에 코드를 작성합니다.
 
  isVisited[from] = true
  if(from === to) return true;
  
  for(let i=0; i<matrix[from].length; i++){
 
    if(isVisited[i] === false && matrix[from][i] === 1){
      let dfs = getDirections(matrix,i,to,isVisited)
      if(dfs){
        return true
      }
    }
  }
  return false;
}