[TIL] 2024-12-12_BFS/DFS

Yuri·2024년 12월 12일

TIL

목록 보기

6/59

📕 Today I Learned - 오늘 내가 공부한 것을 정리합니다.

1. BFS

BFS (Breadth-first-Search, 너비 우선 탐색)

루트 노드(혹은 임의의 다른 노드)에서부터 시작하여 인접한 노드를 먼저 탐색해 나가는 방법
그래프에서 최단 경로를 찾는 정점 기반 알고리즘

위와 같은 그래프가 존재하고 노드의 탐색을 1번 부터 시작.

BFS 알고리즘 그래프 탐색 순서
- 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7

package Algorithm;

import java.util.LinkedList;
import java.util.Queue;

public class Bfs {

    public static void main(String[] args) {
        // 그래프를 2차원 배열로 표현
        // 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않는다.
        // 1번 인덱스는 1번 노드를 뜻하고 노드의 배열의 값은 연결된 노드를 뜻함.
        int[][] graph = {{}, {2, 3, 8}, {1, 6, 8}, {1, 5}, {5, 7}, {3, 4, 7}, {2}, {4, 5}, {1, 2}};

        // 방문 처리를 위한 boolean 배열 선언
        boolean[] visited = new boolean[graph.length];

        System.out.println(bfs(1, graph, visited));
    }

    public static String bfs(int start, int[][] graph, boolean[] visited) {
        // 탐색 순서를 출력하기 위한 용도
        StringBuilder sb = new StringBuilder();
        // BFS에 사용할 큐를 생성
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 BFS를 시작 할 노드 번호를 넣기
        queue.offer(start);
        // 시작노드 방문처리
        visited[start] = true;

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int nodeIndex = queue.poll();
            sb.append(nodeIndex + " -> "); // 노드 순서
            // 큐에서 꺼낸 노드와 연결된 노드들 체크
            for (int i = 0; i < graph[nodeIndex].length; i++) {
                int temp = graph[nodeIndex][i];
                // 방문하지 않았으면 방문처리 후 큐에 넣기
                if (!visited[temp]) {
                    visited[temp] = true;
                    queue.offer(temp);
                }
            }
        }
        // 탐색 순서 리턴
        sb = sb.delete(sb.length() - 3, sb.length()); // 마지막 -> 제거
        return sb.toString();
    }

}

2. DFS

DFS (Depth-first Search, 깊이 우선 탐색)

루트 노드(혹은 임의의 다른 노드)에서부터 시작하여 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식
하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘

위와 같은 그래프가 존재하고 노드의 탐색을 1번 부터 시작.

DFS 알고리즘 그래프 탐색 순서
- 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7

장점

현재 경로상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 든다.
깊이 우선 탐색이 너비 우선 탐색 보다 좀 더 간단하다.
목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

경로의 특징을 저장해둬야 하는 문제나 검색 대상 그래프 문제 등에 사용

package Algorithm;

public class Dfs {
    // 그래프를 2차원 배열로 표현
    // 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않는다.
    // 1번 인덱스는 1번 노드를 뜻하고 노드의 배열의 값은 연결된 노드를 뜻함.
    static int[][] graph = {{}, {2, 3, 8}, {1, 6, 8}, {1, 5}, {5, 7}, {3, 4, 7}, {2}, {4, 5}, {1, 2}};
    static boolean[] visited = new boolean[graph.length];
    static int count;

    public static void main(String[] args) {
        dfs(1);
    }

    static void dfs(int nodeIndex) {
        // 방문 처리
        visited[nodeIndex] = true;
        count++;

        // 방문 노드 출력
        System.out.print(nodeIndex);
        if (count != graph.length - 1) {
            System.out.print(" -> "); // 마지막 -> 출력하지 않음
        }

        // 방문한 노드에 인접한 노드 찾기
        for (int node : graph[nodeIndex]) {
            // 인접한 노드가 방문한 적이 없다면 DFS 수행
            if (!visited[node]) {
                dfs(node); // 재귀
            }
        }
    }
}