본문 바로가기
Algorithm

DFS, BFS with Java

by Gundorit 2022. 9. 14.

우선 간단하게 BFS와 DFS의 정의를 살펴보고 예제를 설명해보겠습니다. 

 

BFS는 너비 우선 탐색이라고 합니다. 

너비 우선 탐색은 시작 정점에서 인접한 정점들을 우선적으로 방문하는 탐색 방법입니다. 

 

그림을 보면서 너비 우선 탐색이 어떻게 탐색을 진행하는지 알아보겠습니다. 

 

시작 정점은 A 입니다.A에서 인접한 정점B, C, D가 있네요. B부터 차례대로 방문 합니다. 

B에 방문했다면 해당 정점에서 인접한 정점이 있는지 확인합니다.

B는 E와 F가 연결되어 있네요. 이 때, E와 F에 바로 방문하는 것이 아닙니다.

우리는 A에서 인접한 정점 B, C, D 를 우선적으로 방문한 뒤 E, F에 방문해야 합니다.

일단 나중에 방문하기로 하고 Queue에 저장합니다. B를 방문한 뒤 C를 방문합니다.

C에서도 F로 갈 수 있네요. 하지만 이 때 F를 또 Queue에 저장하면 안됩니다.

B에서 나중에 방문할 정점들을 Queue에 저장할 때, 따로 방문 여부를 체크합니다. 후에 다른 정점이 해당 노드를 또 저장하는 불상사를 방지하기 위해서요. 

만약 정점에서 더 이상 탐색할 정점이 없다면 별다른 액션을 취하지 않습니다. D, E, 그리고 F가 그런 케이스 입니다. 

 

따라서 BFS의 탐색 순서는 A > B > C > D > E > F 가 됩니다. 

 

그렇다면 BFS를 코드로는 어떻게 구현할까요? BFS는 큐를 이용하여 구현합니다. 아래 코드를 보면서 간략한 설명을 진행해보겠습니다

public static void BFS(int V) {
        Queue<Integer> q = new LinkedList<>();
        ch[V] = 1;
        q.offer(V);
        while (!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur + " ");
            for (int x : graph.get(cur)) {
                if (ch[x] == 0) {
                    ch[x] = 1;
                    q.offer(x);
                }
            }
        }
    }

BFS의 매개 변수로는 시작 정점을 넘겨줍니다. 시작 정점을 체크하고 큐에 저장하기 위해서입니다. 

반복문은 큐가 비어있을 때 까지 진행되며, 큐의 값이 꺼내지는 시점에 꺼내진 정점에서 갈 수 있는 인접 정점들을 큐에 저장합니다. 

이 때 ch[x] == 0 이란 조건문이 보이시나요? 아까 말씀드렸다 싶이, 방문할 예정 혹은 이미 방문한 정점을 또 다시 큐에 저장할 필요가 없습니다. 그렇기에 ch[x] == 0, 즉 한 번도 방문을 안했을 시 큐에 값을 저장합니다. 저장할 때, ch[x] = 1; 로 저장하니 같은 값이 큐에 두번 들어갈 일이 없습니다. 

 

이제 DFS에 대해 알아보도록 하겠습니다. 

DFS는 깊이 우선 탐색이라고 합니다. 하나의 정점에서 시작해서 모든 정점을 탐색합니다. 한 정점을 끝까지 판다고 생각하면 됩니다. 

 

위 BFS와 동일한 형태의 그래프 입니다. 하지만 탐색의 진행 방향은 전혀 다릅니다. 

 

시작 정점 A 에서 갈 수 있는 정점을 살펴봅니다. B로 이동 합니다. 

정점 B에서 갈 수 있는 정점을 살펴봅니다. E로 이동 합니다. 

정점 E는 더이상 이동 할 수 있는 정점이 없습니다.

그렇다면 이제 B에서 F로 이동합니다. 

정점 F에서 C로 이동이 가능합니다. C로 이동합니다. 

정점 C에서 정점 A로 이동 가능하지만, A는 시작 정점으로서 이미 방문했습니다. 더 이상 갈 수 있는 정점이 없습니다. 

정점 A에서 D로 이동합니다. 

 

다소 들쑥날쑥한 정점 탐색을 보이는 이유는 DFS가 재귀적으로 표현되었기 때문입니다. 

하나의 정점으로 부터 왼쪽으로 갈 수 있는 만큼 이동을 한 뒤, 더이상 이동할 수 없다면 오른쪽으로 이동합니다. 

 

코드를 보며 이해해보도록 하겠습니다. 

public static void DFS(int V) {
    ch[V] = 1;
    System.out.print(V + " ");
    for (int x : graph.get(V)) {
        if (ch[x] == 0) {
            DFS(x);
        }
    }
}

예를 들어 DFS(정점 A) 가 호출되었다고 생각해봅시다. 

ch[정점 A] = 1(true); 로 표시 합니다. 

반복문은 정점 A에서 갈 수 있는 정점들을 호출합니다. B, C, D를 호출하겠네요. 

하지만 C, D가 호출되는 시점은 한참 뒤입니다. DFS(B) 함수가 호출되면 DFS(B) 함수 내에서도 또 다른 재귀가 이뤄지기 때문입니다. 

 

예시는 백준 1260번을 사용하였습니다.

아래 코드를 첨부하오니 모르는 부분이 있다면 질문해주시면 감사하겠습니다 :)

import java.io.*;
import java.util.*;

public class Main {
    static public ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    public static void DFS(int V) {
        ch[V] = 1;
        System.out.print(V + " ");
        for (int x : graph.get(V)) {
            if (ch[x] == 0) {
                DFS(x);
            }
        }
    }
    public static void BFS(int V) {
        Queue<Integer> q = new LinkedList<>();
        ch[V] = 1;
        q.offer(V);
        while (!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur + " ");
            for (int x : graph.get(cur)) {
                if (ch[x] == 0) {
                    ch[x] = 1;
                    q.offer(x);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt(), V = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        for (int i = 0; i <= N; i++) {
            Collections.sort(graph.get(i));
        }
        ch = new int[N + 1];
        DFS(V);
        System.out.println();

        ch = new int[N + 1];
        BFS(V);
        System.out.println();
    }
}

댓글