[코딩 테스트 합격자 되기 문제 39] 너비 우선 탐색 순회

문제 설명

너비 우선 탐색으로 모든 그래프의 노드를 순회하는 함수 solution()을 작성하세요. 시작 노드는 start로 주어집니다. graph는 [출발 노드, 도착 노드] 쌍들이 들어 있는 배열입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 너비 우선 탐색으로 진행한 순서대로 노드가 저장된 배열입니다.

 

제약 조건

• 노드의 최대 개수는 100개를 넘지 않습니다.
• 시작 노드부터 시작해서 모든 노드를 방문할 수 있는 경로가 항상 있습니다.
• 그래프의 노드는 숫자입니다.

입출력의 예

graph	start	return
[(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,8),(5,8),(6,9),(7,9)]	1	[1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)]	1	[1,2,3,4,5,0]

 

정답

function solution(graph, start) {
    //그래프를 인접 리스트로
    const adjList = {};
    
    for(const [start,end] of graph){
        if(!adjList[start]) adjList[start] = [];
        adjList[start].push(end);
    }
    
    const visited = new Set(); //방문 여부 처리
    const queue = []; //큐로 bfs를 돌릴거임
    
    queue.push(start);
    visited.add(start); //시작 노드를 바로 방문처리
    const result = [start]; //바로 시작노드 결과배열에 푸쉬
    
    //큐 빌때까지 돌린다
    while(queue.length > 0){
        const node = queue.shift(); //팝해서 인근 노드를 찾을거임
        for(let neighbor of adjList[node] || []){
            if(!visited.has(neighbor)){
                //방문하지않았을 경우 탐색
                queue.push(neighbor);
                visited.add(neighbor);
                result.push(neighbor);
            }
        }
    }
    
    return result;
}