BFS 탐색을 위한 나의 템플릿!

몇날 몇일을 붙잡은 결과 BFS코드를 따라치는게 아니라 내가 직접 디버깅 해가면서 드디어 이해가 되었다 ... 중요한 것 포인트!

• BFS는 큐 자료구조를 이용하며 완전탐색 뿐 아니라 최단경로 찾는 방법으로 사용한다

const graph = {
    'A': ['B', 'D', 'E'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['A', 'B'],
    'E': ['A'],
}

const bfs = (graph, start_v) => {
    let queue = []
    
    //방문 예약할 요소들을 담아 줄 큐 배열
    //먼저 들어온 순서대로 방문해준다
    
    let visited = []
    
    //방문 한 요소들을 기록해 줄 visited 방문완료했단 뜻이다
    
    queue.push(start_v)
    visited.push(start_v)
  
  	//처음으로 방문 예약 된 버택스 노드 등등 여러 이름으로 불리는데 난 노드라해야지
  	//'A'를 제일 먼저 방문하여 거기에 연결 되어있는 노드들을 방문할 것 이다
  
    while (queue.length !== 0) {
      
    //큐 배열엔 방문 예정인 노드들이 대기중 길이가 0이 아니면 실행할 반복문이다
      
        let cur_v = queue.shift();
      
   //가장 앞에 있는 노드는 먼저 방문 할 노드이다 큐배열에선 삭제하고 현제 방문할 노드라는 의미를 가진 해당 변수에 초기화 해준다
      
        for (let i = 0; i < graph[cur_v].length; i++) {
   //이 부분에서 해맸다 외부에 있는 그래프 객체에서 현제 방문 할 노드에 연결되어 있는 노드들을 먼저 방문한다
            if (!visited.includes(graph[cur_v][i])) {
              
/*
visited 배열에는 이미 방문한 노드들이 전부 저장되어 있다 중복되는 것은 
추가해줄 필요가 없고 중복되지 않은 노드들은 큐 배열에 넣어 방문예약을 
해줄 것이고 visited 배열에 넣어 방문을 했다는 기록을 남겨둘 것이다              
*/              
                queue.push(graph[cur_v][i])
                visited.push(graph[cur_v][i])
            }
        }
    }
    console.log(visited)
  //최종적으로 visited 배열에는 BFS로 탐색한 노드들이 남아있게 된다
}


bfs(graph, 'A')

//[ 'A', 'B', 'D', 'E', 'C' ]

코드야 보고 짜면 그만이니 이해하려고 노력했다
디버깅을 하면서 내가 아는 정보로 그리고 내가 이해하기 쉬운 방향으로 코드를 수정하며 올바른 동작을 했을때 짜릿했다 앞으로 이 템플릿을 외워서 가독성도 더 좋은 방향으로 수정하며 문제를 풀 것이야!

const bfs = (graph, start_v) => {
    let queue = []
    let visited = []
    queue.push(start_v)
    visited.push(start_v)
    while (queue.length !== 0) {
        let cur_v = queue.shift();
        for (let i = 0; i < graph[cur_v].length; i++) {
            if (!visited.includes(graph[cur_v][i])) {
                queue.push(graph[cur_v][i])
                visited.push(graph[cur_v][i])
            }
        }
    }
    return visited
}

까먹어도 좌절하지 말고 와서 보고 다시 이해하렴 따스한 나의 벨로그 ..