[알고리즘] DFS와 BFS 다루기

DFS와 BFS는 코딩 테스트에서 항상 단골 문제로 출제되는 매우 중요한 알고리즘 중에 하나이다.

이제부터 어떠한 경우에 DFS와 BFS 문제를 적용하여 문제를 풀이 할 수 있는 지 작성해 본다.

 

 

DFS

깊이 우선 탐색은 그래프 완전 탐색 기법 중에 하나로, 그래프의 시작 노드에서 출발하여, 탐색할 한 쪽 분기를 정해 탐색을 마친 후, 다른 분기로 이동하여 탐색을 하는 알고리즘이다.

 

 

DFS(깊이 우선 탐색)의 특징

- 재귀 함수로 구현한다.(중요)
- 스택 자료구조를 사용한다.

 

 

실제 문제 풀이에서 DFS는 재귀함수를 사용하는 경우가 많은데, 이 때 스택 오버플로우를 주의해야 한다.

DFS 문제에 대한 유형은 주로, 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제이다.

 

 

 

DFS 문제 예시

11724번: 연결 요소의 개수

백준 11724번 문제를 통해 기본적인 DFS 구현 방법을 알 수 있다.

 

 

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<Integer>[] A;
    static boolean visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        A = new ArrayList[N+1];
        visited = new boolean[N+1];
        for(int i=1; i<N+1; i++) {
            A[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        int count = 0;
        for(int i=1; i<N+1; i++) {
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }
    static void DFS(int v) {
        if (visited[v]) {
            return;
        }
        visited[v] = true;
        for(int i: A[v]) {
            if(visited[i] == false) {
                DFS(i);
            }
        }
    }
}

 

DFS나 BFS가 주로 사용되는 문제는 위와 같이 노드와 에지를 사용하는 경우가 많다.

그래서 각 노드들이 어떤 노드와 관계를 가지고 있는 지 연결하여 저장하여야 하는데,

이 때 자바에서는 인접 리스트(ArrayList) 배열을 사용하여 이와 같은 관계를 정의한다.

 

 

- DFS는 재귀 함수를 사용하는 때가 많다.(개념은 스택)

- 방문 배열을 사용하며, 인접 리스트안의 값들을 재귀 함수로 방문하며 탐색한다.

 

 

 

DFS 문제 예시 2

 

2023번: 신기한 소수

 

다음은 백준 2023번 문제를 통해 조금 더 어려운 DFS 문제의 예시를 살펴보자.

해당 문제는 자릿수 별로 탐색을 해나가며, 소수임을 밝혀내는 문제인데,

여기서 DFS를 사용하며 적절한 가지치기와 탐색을 병행하여 진행할 수 있다.

 

 

import java.util.*;
import java.io.*;
public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }

    static void DFS(int num, int jarisu) {
        if(jarisu == n) {
            if (isPrime(num)) {
                System.out.println(num);
            }
        }
        for(int i=1; i<=9; i++) {
            if(i % 2 == 1 && isPrime(num)) {
                DFS(num * 10 + i, jarisu +1);
            }
        }
    }


    static boolean isPrime(int num) {
        for(int i=2; i<=num/2; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

}

 

 

- 첫 번째 자릿수는 소수 그 자체 밖에 못 오므로, 2, 3, 5, 7 만 올 수 있다.

- 그 다음 자릿수는 짝수는 안되므로(10이상의 짝수 중에 소수는 없음), 홀수만 가지치기

- 즉, 이 문제에서의 DFS는 자릿수와 소수 판별을 통해 구성된다.

 

 

 

DFS 문제 예시 3

 

 

13023번: ABCDE

사실 이 문제는 DFS의 개념을 도입할 줄 만 알면, 그렇게 높은 등급의 문제는 아니라고 생각한다.

재귀 깊이 자체가 답을 도출하는 핵심이기 때문이다.

 

 

import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static boolean arrive;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new boolean[n];
        A = new ArrayList[n];

        arrive = false;
        for(int i=0; i<n; i++) {
            A[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        for(int i=0; i<n; i++) {
            DFS(i, 1);

            if(arrive) {
                break;
            }
        }

        if (arrive) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }


    }

    static void DFS(int now, int depth) {
        if (depth == 5 || arrive) {
            arrive = true;
            return;
        }

        visited[now] = true;

        for(int i : A[now]) {
            if (!visited[i]) {
                DFS(i, depth+1);
            }
        }
        visited[now] = false;
    }

}

 

- DFS에서는 연결된 에지에 대해서 재귀함수를 계속 호출할 것이다.

- 이 말의 의미는 호출된 횟수가 친구의 수와 같다면, 친구들끼리는 끊어진 곳 없이 연결되어 있다는 것이다.

- 인접 리스트를 통해서 생각보다 쉽게 풀어줄 수 있다.

 

 

 

---

 

 

 

BFS

 

너비 우선 탐색또한 그래프를 완전 탐색하는 방법 중에 하나이다. 이는 시작 노드에서 출발하여 가까운 노드를 먼저 방문하며 탐색하는 알고리즘이다.

 

BFS(너비 우선 탐색)의 특징

- FIFO 탐색이다.

- Queue 자료구조를 사용한다.

 

 

또한 노드 수(V)와 에지 수(E)에 따라 시간 복잡도가 결정됨은 DFS와 동일하다.(O(V+E))

 

그렇다면 너비 우선 탐색은 깊이 우선 탐색과 어떤 점에서 차이점을 둘까? 그건 바로 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선으로 탐색하기에 목표 노드로 도착하는 경로가 여러개 일 때, 최단 경로를 보장한다.

 

최단 경로를 보장한다는 것은 굉장한 이점이자, 이용할 수 있는 면이 많다는 것을 의미하기도 한다.

 

 

How to Work?

 

이전의 DFS는 재귀함수(스택)를 이용했다. BFS도 이름은 비슷해 보이지만, 똑같은 방식으로 작동되는 것은 분명 아닐 것이다.

 

BFS는 큐 자료구조를 이용한다. 우리가 이전의 DFS는 스택 대신 재귀함수를 사용했지만, BFS는 큐 자료구조 그 자체를 사용해야 간편하다.

 

단, DFS와 동일하게 인접 리스트를 사용하여, 스택(재귀함수)에 집어 넣었던 것과는 별개로 인접리스트를 사용해 큐에 삽입한다는 것이다.

 

 

- BFS는 구현에 있어서 Queue 자료구조를 이용한다.

- BFS도 인접 리스트를 사용한다.

 

 

BFS 문제 예시 1

 

엄밀히 말해서 이 문제는 DFS와 BFS를 모두 사용하는 좋은 예시이다.

 

 

 

 

import java.util.*;
import java.io.*;
public class Main {

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


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        A = new ArrayList[n+1];

        for(int i=1; i<=n; i++) {
            A[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        for(int i=1; i<=n; i++) {
            Collections.sort(A[i]);
        }

        visited = new boolean[n+1];

        DFS(start);

        System.out.println();
        visited = new boolean[n+1];
        BFS(start);
        System.out.println();



    }

    public static void DFS(int Node) {
        System.out.print(Node + " ");
        visited[Node] = true;
        for(int i: A[Node]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    private static void BFS(int Node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        visited[Node] = true;

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

}

 

위 처럼 BFS 구현 시에는 Queue 자료구조를 사용한다.

 

BFS에서는?

- Queue 자료구조를 사용한다.

- 방문 배열을 사용한다.

- queue가 빌 때까지 검사를 하는데, poll 한 값의 인접 리스트를 차례로 방문하며, 큐에 삽입한다.

 

 

 

BFS 문제 예시 2

 

이 문제는 BFS 문제의 대표적인 예시라고 생각한다. 미로 탐색에 관한 문제이다.

 

2178번: 미로 탐색

 

 

import java.util.*;
import java.io.*;
public class Main {

    static int[][] A;
    static int n, m;
    static boolean[][] visited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        A = new int[n][m];
        visited = new boolean[n][m];


        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0; j<m; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }

        BFS(0, 0);
        System.out.println(A[n-1][m-1]);
    }

    public static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { i, j});
        visited[i][j] = true;
        while(!queue.isEmpty()) {
            int now[] = queue.poll();
            for(int k=0; k<4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >=0 && x<n && y<m) {
                    if(A[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;
                        queue.add(new int[] { x, y });
                    }
                }
            }
        }

    }

}

 

개념만 제대로 숙지하는 고수님들은 쉽게 생각해 낼 수 있지만, 알고리즘에 익숙치 않은 이들에게는 생소한 방식이다.

입력 받는 부분도 파이썬으로 한다면, 간단하게 할 수 있는 부분이다. 하지만, StringTokenizer와 substring을 통해서 하나 하나 받는 방식은 번거롭기도 하고, 손목 관절에 악영향을 미치기도 한다.(물론 난 코딩 고수가 된 것 같은 느낌이어서 좋다.. 하하)

 

- 방향 벡터를 사용하자.(dx와 dy를 선언해 줌으로써, for문으로 쉽게 방문 절차를 만들 수 있다.)

- Queue의 각 요소는 행과 열의 각 index 값을 가진 값이다. 그래야, 각각의 미로 지점 자체를 방문 지점으로써, 선언할 수 있기 때문이다.


- 이제 BFS의 동작 방식은 동일한다. 단, poll 한 값을 기반으로 인접 리스트가 있는 것이 아닌, 방향 벡터 for문을 돌려, 각각 탐색을 이어나간다.

- 범위 체크도 해주어야 한다.

- 탐색을 완료한 지점은 +1씩 정답 배열에 더해주며, queue에 삽입한다.

 

 

 

BFS 문제 예시 3

 

마지막 BFS 문제이다. 이 문제는 일반적으로 BFS를 사용하는 것 외에 많은 생각을 필요로 한다.

 

1167번: 트리의 지름

 

 

import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Edge>[] A;
    static int n, m;
    static boolean[] visited;
    static int[] distance;


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        A = new ArrayList[n+1];

        for(int i=1; i<=n; i++) {
            A[i] = new ArrayList<Edge>();
        }
        for(int i=0; i<n; i++) {
            int S = sc.nextInt();
            while(true) {
                int E = sc.nextInt();
                if (E == -1) {
                    break;
                }
                int V = sc.nextInt();
                A[S].add(new Edge(E, V));
            }
        }
        distance = new int[n+1];
        visited = new boolean[n+1];
        BFS(1);
        int Max = 1;
        for(int i=2; i<=n; i++) {
            if (distance[Max] < distance[i]) {
                Max = i;
            }
        }


        distance = new int[n+1];
        visited = new boolean[n+1];
        BFS(Max);
        Arrays.sort(distance);
        System.out.println(distance[n]);
    }

    private static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        while(!queue.isEmpty()) {
            int now_node = queue.poll();
            for(Edge i : A[now_node]) {
                int e = i.e;
                int v = i.value;
                if(!visited[e]) {
                    visited[e] = true;
                    queue.add(e);
                    distance[e] = distance[now_node] + v;
                }
            }
        }
    }



}
class Edge {
    int e;
    int value;

    public Edge(int e, int value) {
        this.e = e;
        this.value = value;
    }
}

 

 

이 문제가 어려운 이유는 가중치라는 것이 존재하는 것도 있긴 하다.

그래프에서 노드와 노드 사이(에지)에 가중치라는 것이 더해지면, 답의 기준이 바뀌곤 한다.

 

자바에서는 이를 표현하기 위해 클래스로 에지를 두어, 노드와 가중치를 한 번에 초기화 할 수 있도록 했다.

 

- ArrayList의 제네릭 타입은 Edge이다.

- 임의의 노드에서 가장 긴 경로로 연결되어 있는 노드는 트리의 지름에 해당하는 두 노드 중에 하나이다.

- 즉, 거리 배열을 만들어 이 과정을 수행할 수 있다.

- BFS는 결국 탐색 알고리즘이다. 해당 노드까지 갈 수 있는 탐색 거리(가중치)를 더해가며, 거리 배열을 완성할 수 있다.

- BFS를 두 번 하는 이유는, 첫 번째 임의의 노드에서 찾은 모든 노드에 대한 거리 중 가장 긴 거리가 바로 트리의 지름에 해당하는 두 노드 중 하나인 것이고,

이 노드의 BFS를 수행함을 통해, 가장 멀리 떨어진 노드까지의 거리를 알아낼 수 있기 때문이다.

 

 

BFS는 최단 거리를 구할 수 있을 뿐만 아니라,
탐색 경로에 대한 가중치를 더해 가며, 원하는 탐색 대상도 찾을 수 있다는 것이다.

 

 

 Reference

- Do it! 코딩 테스트 - 기초 편