[알고리즘] Java로 BFS, DFS 파헤치기

들어가며..

이번 포스팅은 코딩테스트에 단골로 나온다는 BFS, DFS 알고리즘에 대해서 다뤄보려고 해요.

BFS, DFS 카테고리 문제들을 풀어보면서 한번 정리해서 글로 작성하는게 좋을 것 같다고 생각했어요.

BFS, DFS란 무엇인지, 코드로는 어떻게 구현할 수 있는지, 어떻게 활용할 수 있을지를 그림과 함께 쉽게 설명 해볼게요.

---

 

 

그래프 (Graph) 란?

먼저 BFS, DFS 알고리즘을 정리하기 전에, 그래프 자료구조에 대해서 알아야 해요!

 

위 그림을 보시면 동그라미로 표현되어 있는 노드가 존재하고 이러한 노드는 간선으로 연결되어 있다는 것을 알 수 있어요.

이러한 특성을 이용하면 노드끼리 연결되어 있으니, 하나의 노드를 참조하면 연결되어 있는 다른 노드를 참조하는 것이 가능하겠죠? 따라서, 그래프는 노드끼리 간선을 통해 연결 되어있는 자료구조를 말해요.

 

그래프를 나타내는 방식에는 여러 가지 종류가 있지만, 이번 포스팅은 알고리즘이 중심이므로 다음에 소개할게요.

밑의 알고리즘 코드 구현에서 사용될 그래프 자료구조를 JAVA 언어를 이용해서 다음과 같이 간단하게 구현했어요.

public class Node {
    int val;
    // 연결된 노드 리스트
    List<structure.Node> connectionNodes;

    public Node(int val) {
        this.val = val;
        connectionNodes = new ArrayList<>();
    }
}

---

 

 

그래프 탐색 알고리즘

이제 그래프 자료구조에 대해서 설명했으니, 탐색 알고리즘인 BFS, DFS에 대해서 설명할게요.

 

 

BFS 란?

너비 우선 탐색 BFS (Breath First Search)는 그래프를 넓이 중심으로 탐색한다는 것을 의미해요.

사실 모든 알고리즘은 말로 설명하는 것보다, 코드와 그림으로 설명하는 것이 더 이해하기 쉽고 머리에 잘 남는것 같아요.

BFS 탐색 방법은 노드를 중심으로 자신에게 연결된 노드들을 먼저 모두 방문하는 방식이에요.

Java 코드로 다음 알고리즘을 구현해볼까요?

class BFS {
    void bfs(Node node, Set<Node> visited) {
        // 노드를 저장하고 꺼낼 큐 선언
        Deque<Node> queue = new ArrayDeque<>();

        // 시작 노드 추가 및 방문 기록
        queue.add(node);
        visited.add(node);

        // 큐가 비어있을 때 까지
        while (!queue.isEmpty()) {
            Node pollNode = queue.poll();
            System.out.printf("%d ", pollNode.val);

            // 연결되어 있는 노드 모두 탐색
            for (Node connectionNode : pollNode.connectionNodes) {
                // 이미 방문 했던 노드라면 skip
                if (visited.contains(connectionNode)) continue;

                // 방문한 노드 기록
                visited.add(connectionNode);
                // 큐에 추가
                queue.add(connectionNode);
            }
        }
    }
}

 

이렇게 방문한 노드 순서대로 먼저 꺼내서 처리를 하기 위해서는 큐 자료구조를 이용하는게 적합해요.

 

 

시간 복잡도

BFS 시간 복잡도는 노드의 갯수 n개, 간선의 갯수 e개 라고 가정했을 때, 모든 노드와 간선을 참조하므로 O(n+e)가 돼요.

 

 

DFS 란?

깊이 우선 탐색 DFS (Depth First Search)는 BFS와 다르게 그래프를 깊이 중심으로 탐색하는 것을 의미해요.

이것도 같이 그림으로 보면서 이해해봐요.

DFS 탐색 방법은 다음과 같이 노드를 타고타고 내려가는 방식이에요.

이것도 코드로 한번 나타내볼게요.

class DFS {
    void dfs(Node node, Set<Node> visited) {
        // 방문한 노드 기록
        visited.add(connectionNode);

        System.out.printf("%d ", node.val);

        // 연결되어 있는 노드 모두 탐색
        for (Node connectionNode : node.connectionNodes) {
            // 이미 방문 했던 노드라면 skip
            if (visited.contains(connectionNode)) continue;

            // 연결된 노드 기준으로 재귀 함수 호출
            dfs(connectionNode, visited);
        }
    }
}

 

BFS 보다 코드가 짧죠? 그 이유는 재귀 방식을 이용해서 코드를 간결화 시켰기 때문이에요.

DFS는 노드를 방문하다가 자신에게 연결된 노드가 없을 때, 연결된 노드가 남아있는 이전 노드로 돌아가야만 하기 때문에 상태를 기억해야 해요. 따라서 다음과 같이 재귀 방식을 이용하면 간단하게 구현할 수 있어요. 만약 재귀 방식이 싫다고 하시면, 다음과 같이 스택 방식으로 구현을 할 수 있어요.

class DFS {
    void dfsWithStack(Node startNode, Set<Node> visited) {
        Deque<Node> stack = new ArrayDeque<>();

        stack.push(startNode);
        visited.add(startNode);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.printf("%d ", node.val);

            for (Node connectionNode : node.connectionNodes) {
                if (visited.contains(connectionNode)) continue;

                visited.add(connectionNode);
                stack.push(connectionNode);
            }
        }
    }
}

 

스택으로 작성하고보니, BFS 방식과 코드가 매우 비슷하다는 것을 알 수 있어요. 유일한 차이점은 큐와 스택 활용 차이라고 볼 수 있겠네요.

 

 

시간 복잡도

DFS도 마찬가지로 노드의 갯수 n개, 간선의 갯수 e개 라고 가정했을 때, 모든 노드와 간선을 참조하므로 O(n+e)가 돼요.

사실 탐색 알고리즘이니까 당연히 BFS와 DFS 모두 시간 복잡도가 같겠죠?

---

 

 

문제 풀이

이제 BFS와 DFS 알고리즘에 대해서 배웠으니, 대표적인 문제 몇 가지를 풀어볼까 해요.

 

 

BFS 활용 문제 풀이

BFS는 가중치가 없는 그래프에서 최단 경로를 찾을 때 매우 유용해요.

그 이유는 넓이 우선 탐색 방식이기 때문에 조건에 맞는 노드를 찾았을 때 결과 값을 반환할 수 있기 때문인데요.

간단한 예시로, 백준의 미로 탐색 이라는 문제를 같이 볼까요?

 

문제에서 요구하는건 시작 위치 (1, 1)부터 도착 위치 (N, M)으로 도착할 때 까지 최단 길이를 반환하면 되네요. 한번 직접 풀어보시고 더보기를 눌러 코드를 보시면 좋을 것 같아요.

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

class Cell {
    int x;
    int y;
    // 경로 길이
    int length;

    public Cell(int x, int y, int length) {
        this.x = x;
        this.y = y;
        this.length = length;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] lengthLine = reader.readLine().split(" ");
        int height = Integer.parseInt(lengthLine[0]);
        int width = Integer.parseInt(lengthLine[1]);
        int[][] maze = new int[height][width];
        int answer = 1;

        Queue<Cell> queue = new LinkedList<>();
        boolean[][] visited = new boolean[height][width];
        // 상, 하, 좌, 우를 나타내는 배열
        int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // 데이터 초기화
        for (int i = 0; i < height; i++) {
            String[] pathLine = reader.readLine().split("");
            for (int j = 0; j < width; j++) {
                maze[i][j] = Integer.parseInt(pathLine[j]);
            }
        }

        // bfs
        queue.add(new Cell(0, 0, 1));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
        	// 현재 큐 앞에 있는 위치가 도착 위치라면
            if (queue.peek().x == height - 1 && queue.peek().y == width - 1) {
                break;
            }

            Cell cell = queue.poll();
            int x = cell.x;
            int y = cell.y;
            
            // 상, 하, 좌, 우 이동
            for (int i = 0; i < 4; i++) {
                int dx = x + direction[i][0];
                int dy = y + direction[i][1];

				// 배열의 범위를 벗어났을 때
                if (dx < 0 || dy < 0 || dx >= height || dy >= width) continue;
                // 길이 아니거나, 이미 방문했던 위치일 때
                if (maze[dx][dy] != 1 || visited[dx][dy]) continue;

                queue.add(new Cell(dx, dy, cell.length+1));
                visited[dx][dy] = true;
            }
            answer++;
        }

        System.out.println(queue.poll().length);
    }
}

 

최단 경로 문제를 하나만 더 풀어볼까요? 조금 더 난이도가 있는 프로그래머스의 단어 변환 문제를 풀어볼게요.

한 번에 한 개의 문자를 알파벳으로 바꿔서 begin에서 target 문자열이 될 수 있는 최소 변환 횟수를 구하는 문제에요.

import java.util.*;

class Word {
    String word;
    // 변환 횟수
    int depth;

    public Word(String word, int depth) {
        this.word = word;
        this.depth = depth;
    }
}

class Solution {
    static boolean[] visited;
    static Queue<Word> queue = new LinkedList<>();
    
    public static int solution(String begin, String target, String[] words) {
        int answer = 0;
        visited = new boolean[words.length];

        queue.add(new Word(begin, 0));

        answer = bfs(words, target);

        return answer;
    }

    public static int bfs(String[] words, String target) {
        while(!queue.isEmpty()) {
            Word source = queue.poll();

			// 해당 단어가 목표 단어와 일치하는 경우
            if (source.word.equals(target)) {
                return source.depth;
            }

            for (int i = 0; i < words.length; i++) {
           		// 해당 단어를 방문하지 않았고 변환이 가능한 경우
                if (!visited[i] && isPossibleChange(source.word, words[i])) {
                    queue.add(new Word(words[i], source.depth+1));
                    visited[i] = true;
                }
            }
        }

        return 0;
    }

    public static boolean isPossibleChange(String source, String target) {
        int answer = 0;
		
        // 문자를 하나씩 비교
        for (int i = 0; i < source.length(); i++) {
            if (source.charAt(i) != target.charAt(i))
                answer++;
        }

		// 문자가 하나만 다를 경우
        return answer == 1;
    }
}

 

 

DFS 활용 문제 풀이

DFS는 스택 또는 재귀를 활용해서 깊이 중심의 탐색을 마치고 반환하는 값을 이용해서 문제를 풀이하는 경우가 많았어요.

 

괜찮았던 문제인 Leetcode Diameter of Binary Tree 문제를 한번 살펴볼게요.

여기서 트리 라는 자료구조가 나오는데요. 해당 자료구조도 결국 그래프 자료구조의 일종으로, 계층적인 구조를 가진다는 특징이 있어요. 자세한 설명은 다음에 따로 포스팅을 작성하도록 할게요.

 

문제에서는 왼쪽 자식 노드와 오른쪽 자식 노드만 가지는 Binary Tree 연결 정보가 주어졌을 때, 한 붓 그리기와 같이 최대 길이 경로를 구하는 문제에요. 재귀에 익숙치 않으면 풀이가 조금 어려울거에요.

public class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        calcMaxDiameter(root);
        return max;
    }

    public int calcMaxDiameter(TreeNode root) {
        if (root == null) return 0;

		// 현재 root의 왼쪽 자식 기준 경로 길이를 가져온다
        int left = calcMaxDiameter(root.left);
        
        // 현재 root의 오른쪽 자식 기준 경로 길이를 가져온다
        int right = calcMaxDiameter(root.right);

		// 왼쪽 자식과 오른쪽 자식의 경로 길이 합과 max를 비교한다
        max = Math.max(max, left + right);

		// 부모 노드에게 자기 자신을 포함하여 최대 경로 길이를 반환한다
        return Math.max(left, right) + 1;
    }
}

 

처음에 위의 문제를 풀 때, 난이도는 easy인데도 불구하고 상당히 어려웠던 기억이 있네요.

 

다음은 비슷하지만 조금 더 난이도가 있는 문제를 풀어볼까해요. LeetCode의 Binary Tree Maximum Path Sum 문제를 같이 볼게요. 똑같은 조건이지만 이번엔 최대 경로 길이가 아닌, 한 붓 그리기를 진행했을 때, 노드들의 합이 최대가 되는 값을 구하라는 문제인데요. 위의 코드를 조금만 응용하면 감을 잡으실거에요.

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root) {
        if (root == null) return 0;
		
        // 왼쪽 자식 기준 최댓 값
        int left = dfs(root.left);
        
        // 오른쪽 자식 기준 최댓 값
        int right = dfs(root.right);

		// 자기 자신, 자기 자신 + 왼쪽 자식, 자기 자신 + 오른쪽 자식 비교한 최댓값
        int rootMax = Math.max(root.val, Math.max(root.val + left, root.val + right));
	
    	// 현재 노드 기준 최댓값
        max = Math.max(max, Math.max(root.val + left + right, rootMax));

        return rootMax;
    }
}

 

위 문제의 핵심은 노드의 값이 음수가 될 수 있다는 점 이었어요.

---

 

 

 

마치며..

지금까지 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대해 살펴보았어요. 이 두 알고리즘은 그래프나 트리 구조의 데이터를 탐색하는 기본적이면서도 강력한 방법인데요. 이 두 알고리즘을 완전히 이해하기 위해서는 직접 구현해보고 다양한 문제에 적용해보는 것이 가장 좋아요. 코딩 테스트 플랫폼이나 알고리즘 문제 사이트에서 관련 문제를 더 많이 풀어보면서 감을 잡는게 가장 중요할 것 같다는 생각이 드네요.

 

 

 

---

 

 

참고 자료

Graph Data Structures in JavaScript for Beginners