[코딩 테스트 합격자 되기 문제 38] 깊이 우선 탐색 순회

문제 설명

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

 

제약 조건

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

입출력의 예

graph	start	return
[['A','B'], ['B','C'], ['C','D'], ['D', 'E']]	'A'	['A','B','C','D','E']
[['A','B'],['A','C'],['B','D'],['B','E'],['C','F'],['E','F']]	'A'	['A','B','D','E','F','C']

 

정답

function solution(graph, start) {
    //그래프를 인접 리스트로 변환
    const adjList = {};
    
    for(const [start,end] of graph){
        if(!adjList[start]) adjList[start] = []; //없으면 우선 빈배열 대입
        adjList[start].push(end); //도착하는 노드를 push
    }
    
    function dfs(node, visited, result){
        visited.add(node); //방문할 노드를 visited에 추가
        result.add(node); //방문한 순서를 결과에 추가
        (adjList[node] || []).forEach((neighbor) => {
            //인접한 애들을 탐색
            if(!visited.has(neighbor)) dfs(neighbor, visited, result); //방문안했으면 탐색
        })
    }
    
    const visited = new Set(); //방문여부
    const result = []; //반환할 결과
    dfs(start, visited, result);
    
    return result;
}