[JAVA] DFS, BFS

DFS, BFS 란?

• DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함
• BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함

• 다음과 같은 그래프를 탐색한다고 가정

DFS 수행 과정

1. 1번 노드에서 시작
2. 2, 5번 노드로 갈 수 있음
3. 숫자가 더 작은 2번 노드로 감 (전략은 마음대로 설정)
4. 3, 4번 노드로 갈 수 있음
5. 3번 노드로 감
6. 3번 노드에서는 갈 수 있는 곳이 없음
7. 2번노드로 돌아감
8. 4번 노드로 감
9. 4번 노드에서 갈 수 있는 곳이 없음
10. 2번 노드로 돌아감
11. 2번 노드에서도 더 이상 갈 수 있는 곳이 없음
12. 1번 노드로 감
13. ....

• 이런 식으로 탐색을 진행
  • 결과 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

BFS 수행 과정

1. 1번 노드에서 시작
2. 2, 5번 노드로 갈 수 있음
3. 갈 수 있는 모든 경로를 큐에 삽입
4. 2번 노드에서 갈 수 있는 모든 경로를 큐에 삽입
5. 5번 노드에서 갈 수 있는 모든 경로를 큐에 삽입
6. 3, 4, 6, 9 노드에서 갈 수 있는 모든 경로를 순서대로 큐에 삽입
7. ....

• 이런 식으로 탐색을 진행
  • 결과 : 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 9 -> 7 -> 8
• DFS는 재귀함수, BFS는 Queue로 구현이 가능
• 시간 복잡도는 DFS, BFS 둘 다 O(V+E)로 같지만 ( V : 노드의 수, E : 에지의 수 )
• 일반적으로 BFS가 조금 더 빠름
• 일반적으로 경로의 특징을 저장해야 하는 경우에는 DFS, 최단 경로를 구하는데에는 BFS를 사용
• 문제에 따라 알맞는 알고리즘 선택이 중요

DFS, BFS 구현

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

• 이 문제를 풀면서 DFS와 BFS를 구현해봄

코드

import java.util.*;

public class p1260 {

    static ArrayList<Integer>[] connections;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        connections = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            connections[i] = new ArrayList<Integer>();
        }

        for(int i = 0 ; i < m ; i ++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            connections[x].add(y);
            connections[y].add(x);
        }

        for(int i = 1 ; i <= n ; i ++) {
            Collections.sort(connections[i]);
        }
        /*  여기까지는
        입력     =>  connections  으로 만드는 과정
        4 5 1       1 => 2 3 4
        1 2         2 => 1 4
        1 3         3 => 1 4
        1 4         4 => 1 2 3
        2 4
        3 4
         */

        dfs(v);
        Arrays.fill(visited, false);
        bfs(v);
    }

    public static void dfs(int Node) {
        System.out.print(Node + " ");
        visited[Node] = true;
        for(int i : connections[Node]) {
            if(visited[i] == false) {
                dfs(i);
            }
        }
        System.out.println();
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(v);
        visited[v] = true;

        while(!queue.isEmpty()) {
            int Node = queue.poll();
            System.out.print(Node + " ");
            for(int i : connections[Node]) {
                if(visited[i] == false) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}