[Algorithm Tech] BFS vs DFS

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

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
• Queue로 구현
• 간선에 가중치가 없는 그래프에서는 방문하는 depth가 최단거리가 된다
• 주로 격자판, 최단거리 구할 때 사용
• while (!q.isEmpty()) -> if (!visited[q.poll()]) -> q.add 순서의 메소드 진행

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

• 재귀로 구현(코드가 간단)
• 자식 노드의 수를 파악하기 편리
• 주로 Tree에서 사용
• dfs 재귀함수에 탈출조건과 재귀내용 작성

* 주요개념

ArrayList의 배열로 구현이 필요

정점의 개수(N)만큼 ArrayList 배열을 만들고, M개의 간선을 N번째 index에 추가

ArrayList<Integer>[] edge = new ArrayList[n+1];
for (int i = 0; i <= n; i++) {
    edge[i] = new ArrayList<>();
}   //ArrayList 추가
 
for (int i = 0; i < m; i++) {
    stk = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(stk.nextToken());
    int v = Integer.parseInt(stk.nextToken());
 
    edge[u].add(v);        // u 정점에 v로 가는 간선 추가
    edge[v].add(u);        // v 정점에 u로 가는 간선 추가
}

* 소스 코드(백준 1260번 DFS와 BFS)

import java.io.*;
import java.util.*;
 
public class Main {
    public static ArrayList<Integer> alist = new ArrayList<>();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());
        int vv = Integer.parseInt(stk.nextToken());
 
        ArrayList<Integer>[] edge = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            edge[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            edge[u].add(v);
            edge[v].add(u);
        }
 
        for (int i = 0; i < edge.length; i++) {
            Collections.sort(edge[i]);
        }
 
        //DFS
        dfs(vv, edge, new boolean[n+1]);
        System.out.println();
 
        //BFS
        alist = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(vv);
        while (!q.isEmpty()) {
            int tmp = q.poll();
            if (!visited[tmp]) {
                visited[tmp] = true;
                System.out.print(tmp + " ");
                for (int i = 0; i < edge[tmp].size(); i++) {
                    q.add(edge[tmp].get(i));
                }
            }
        }
    }
 
    //DFS
    public static void dfs(int v, ArrayList<Integer>[] edge, boolean[] visited) {
        if (!visited[v]) {
            alist.add(v);
            visited[v] = true;
            System.out.print(v + " ");
            for (int i = 0; i < edge[v].size(); i++) {
                dfs(edge[v].get(i), edge, visited);
            }
        }
    }
}