the others/Algorithm

[ Graph - BFS ] 인접 행렬 길 찾기

ciocio 2021. 10. 13. 19:33

✅  BFS 기초 개념 잡기

 

https://blog.naver.com/wpghks7/221598474816

BFS의 기초 개념을 잘 설명해놓은 블로그가 있어 첨부한다.

 

📍  제한 사항

 

주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.

 

 

📍  예시

 

const result = getDirections(
  [
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 1, 0, 0]
  ],
  0,
  2
);

console.log(result)   // true

 

 

📍  코드 공부

정점의 형태 1

 

0과 2는 직접적으로 연결되어있지는 않다.

그러나 둘은 간선으로 연결되어있으므로 true 를 반환하도록 식을 짜야한다.

어떻게 해야할까 ??

정점의 형태 2

 

그리고 만약 첫번째 간선에서 원하는 결과가 탐색되지 않았을 때 두번째 간선으로 넘어가 탐색할 수 있는 로직이 필요하다.

어떻게 해야할까 ??  -->  내가 첫번째 시도에서 놓쳤던 부분이기도 하다.

 

// 틀렸던 코드

matrix의 배열을 돌면서 요소가 1인 인덱스를 따라갔을 때, 
원하는 노드에 1이 있으면 true를 리턴하도록 했다. + 그렇지 않을 경우엔 false를 리턴

그런데 이 경우는, 첫번째 간선에서 원하는 결과를 얻지 못하면 섣불리 false를 리턴하고
반복문을 없앤다는 큰 단점이 있었다. -> 모든 노드들을 완벽하게 탐색하지 못함.

모든 노드들을 빠짐없이 방문하여 최대한 깊게 깊게 탐색할 수 있는 방법은 없을까 >?>?
-> Queue를 통해 검색해야하는 요소들을 꾹꾹 넣어줘서
-> Queue가 비어있을 때 비로소 반복문을 끝내도록 하면 어떤가.

 

// 해결한 코드

function getDirections(matrix, from, to){
  // 탐색해야하는 노드를 담을 Queue를 선언한다.
  // Queue가 비어있으면 반복문이 작동하지 않으므로, 첫번째 요소를 담아준다.
  let queue = [from];
  
  // Queue의 동작을 도와줄 함수를 선언하였다.
  // 값을 넣어주는 enqueue와 값을 빼주는 dequeue
  let enqueue = (n) => queue.push(n);
  let dequeue = () => queue.shift();
  
  // 탐색이 끝난 노드를 표시할 배열을 선언한다.
  // 우리는 머리속으로 해당 노드가 탐색되었다는 걸 알지만, 컴퓨터는 알지 못함..기록 기록
  let checked = new Array(matrix.length).fill(false);
  
  // 제일 먼저 탐색할 노드니까, true로 변경해주기
  checked[from] = true;
  
  // queue가 비어있지 않을 때 계속 실행
  while(queue.length > 0){
  	
    // 01 Queue에 있는 "탐색할 노드"를 꺼내준다.
    let temp = dequeue();
    
    // 03 Queue에 있는 "탐색할 노드"가 to와 일치한다면 true를 반환한다.
    // -> 0을 탐색하며 1을 넣고, 1을 탐색하며 2를 넣게되기 때문에 결국
    // -> 탐색해야하는 노드와 to는 일치하게 된다. 
    if(temp === to) return true;
    
    // 02 for문을 돌면서 temp 배열(노드)를 탐색한다. 
    for(let i=0; i<matrix[temp].length; i++){
    	// temp 배열의 요소중 1이면서 (0이 아니면서 === 노드가 있으면서)
        // 해당 노드를 아직 탐색하지 않았을 때 (값이 false 일때)
        // 두 조건을 만족하는 노드를 Queue에 담아준다. 
    	if(!checked[i] && matrix[temp][i]){
        	enqueue(i);
            checked[i] = true;
        }
    }
  }
  
  // 04 물론 일치하지 않는다면 false를 반환한다.
  return false;
  
}

 

 

📌  풀면서 느낀점

 

Queue를 실전처럼(?) 코드에 적용해본게 처음이다.

이럴 때 이런 알고리즘이 쓰이는구나를 체감해 나가는중.

모든 노드들을 탐색하고 싶다는, 또 한 노드를 깊게 깊게 탐색하고 싶다는 욕망이 해결의 실마리였다. 

반응형