[2023-09-27] 자료구조 & 알고리즘 - BFS,DFS

 

너비 우선 탐색(BFS)

-그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘

 

BFS의 특징

- Queue를 이용하여 구현할 수 있다.

- 시작 지점에서 가까운 정점부터 탐색한다.

- V가 정점의 수, E가 간선의 수 일 때 BFS의 시간복잡도는 O(V+E)이다.

 

깊이 우선 탐색(DFS)

- 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

 

DFS의 특징

- Stack을 이용하여 구현할 수 있다.

- 시작 정점에서 깊은 것부터 찾는다.

- V가 정점의 수, E가 간선의 수 일 때 DFS의 시간복잡도는 O(V+E)이다.

 

 

 

코딩테스트 DFS 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

내 제출

function solution(n, computers) {
    let visited = [false];
    let answer = 0;

    function dfs(i) {
        visited[i] = true;
        for(let j=0; j<computers[i].length; j++) {
            if(computers[i][j]===1 && !visited[j]){
                dfs(j);
            }
        }
    }
    
    for (let i=0; i < computers.length; i++) {
        if (!visited[i]) {
            dfs(i)
            answer++;
        }
    }
    console.log(visited)
    return answer;
}

 

다른 풀이

// DFS 함수를 만듭니다.
function dfs(n, computers, visited, start) {
    const stack = [start]; // DFS의 시작점을 미리 초기화 합니다.

    while (stack.length > 0) { // 탐색이 끝날 때 까지 루프를 돌립니다.
        const curr = stack.pop(); // 요소를 하나 뽑습니다.

        visited[curr] = true; // 이미 탐색한 곳은 다음에 탐색을 방지하기 위해 체크합니다.

        for (let i = 0; i < n; i += 1) { // 탐색 가능한 곳을 찾습니다.
            if (!visited[i] && computers[curr][i]) {
                stack.push(i); // 가능하다면 스택에 추가합니다.
            }
        }
    }
}

function solution(n, computers) {
    let answer = 0;
    const visited = new Array(n).fill(false); // 방문한 노드를 기록하기 위한 배열을 선언합니다.

    for (let i = 0; i < n; i += 1) { // 노드 수 만큼 루프를 돌립니다.
        if (!visited[i]) { // 아직 방문하지 않은 곳이 있다면
            dfs(n, computers, visited, i); // 탐색합니다.
            answer += 1; // 영역 하나를 찾았으므로 하나 더해줍니다.
        }
    }

    return answer;
}

 

코딩테스트 DFS 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

내 제출

function solution(tickets) {
    tickets.sort(); // 글자순 정렬
    let vis=Array(tickets.length).fill(false);
    var answer = [];
    function dfs(cur,cnt,path){
        if(cnt===tickets.length && answer.length===0){ //정렬했으므로 처음오는 경우의 수가 답
            answer=path;
            return;
        }
        for(let i=0;i<tickets.length;i+=1){
            if(!vis[i] && tickets[i][0]===cur){ // 출발하는 공항이 같다.
                vis[i]=true;
                dfs(tickets[i][1],cnt+1,[...path,tickets[i][1]]);//배열 복사해서 넣어주기
                vis[i]=false;
            }
        }
    }
    dfs("ICN",0,["ICN"])
    return answer;
}

 

다른 풀이

function solution(tickets) {
    // 인접 리스트로 그래프를 구성합니다.
    const graph = {}
    for (const [src, dest] of tickets) {
        if (graph[src] === undefined) {
            graph[src] = [];
        }
        graph[src].push(dest);
    }
    
    for (const key in graph) {
        // 역순으로 문자열들을 정렬합니다.
        graph[key].sort((a, b) => a > b ? -1 : 1);
    }
    
    const stack = ['ICN']; // DFS를 위한 스택
    const answer = []; // 경로를 저장하기 위한 리스트
    while (stack.length > 0) { // DFS 시작
        const src = stack[stack.length - 1]; // Top 요소를 확인합니다.
        
        // 갈 수 있는 경로가 있다면
        if (graph[src] && graph[src].length > 0) {
            // 갈 수 있는 경로 중 알파벳 순으로 앞선 것을 먼저 방문합니다.
            // 역순으로 정렬했기에 pop을 하면 알파벳 순입니다.
            stack.push(graph[src].pop());
        } else { // 더 이상 갈 수 있는 경로가 없다면
            // 경로를 추가합니다.
            answer.push(stack.pop());
        }
    }
    
    // 스택 결과를 넣은 것이기 때문에 역순으로 결과를 반환합니다.
    return answer.reverse();
}