코테연습 - bfs/dfs

이번에는 코테 알고리즘인 bfs/dfs 에 대해 알아볼것이다.

 

bfs와 dfs 는 그래프탐색 방법 중 하나로, 어떤 노드를 방문할 때 그 방법이 다르다는 것이다.

bfs 와 dfs 의 노드 방문 방법은 다음 그림과 같다.

 

자 그러면 bfs/dfs 문제에서 어떤 문제에서 어떤 알고리즘을 적용해야할까 고민일것이다. 일단 두 방법으로 모두 풀 수는 있지만

시간제한 때문에 한가지 알고리즘으로 풀어야하는 경우도 존재할 것이다. 그러한 경우를 생각하며 bfs/dfs 를 설명해볼것이다.

 

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

우선 탐색 순서는 가까운 노드부터 탐색한다. 자료구조는 Queue를 이용한다 큐는 알다시피 FIFO(First In First Out) 선입선출의 자료구조이다.

왜 큐 자료구조를 사용하는가?

그 이유는 가까운 노드부터 탐색 해야 하기 때문에 선입선출 방식이 필요하다는 것이다.

설명은 간단하게 돼있지만 그래서 이걸 코테에서 어떻게 적용하라는건데? 라는 생각이 들것이다. 물론 답은 반복해서 풀어보는것 말곤 없을것이다. 하지만 간단한 가이드라인이 될만한 예시코드를 함께 참조하면 좋을것이다.

public class BFS_Example {
    public static void bfs(List<Integer>[] graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 가장 먼저 들어온 노드 꺼내기
            System.out.print(node + " ");  // 방문한 노드 출력

            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next); // 인접한 노드 추가
                }
            }
        }
    }
}

 

위의 코드와 같이 큐에 탐색 시작지점을 queue.offer()을 통해서 넣어준다. 그 후 더이상 방문할 노드가 없을때 까지이니 while 문을 통해 반복을 할것이다. 먼저 queue.poll()을 통해 가장 먼저 들어온 노드를 꺼내고 해당 노드의 인접한 노드들을 추가 해주면 된다. 더 이상 방문할 노드가 없으면 while문의 조건에 의해서 반복이 종료될것이다. 반복이 종료됐다는건 탐색이 끝까지 진행됐다는것이므로 탐색이 종료된것이다.

 

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

다음은 깊이 우선 탐색이다. 현재 노드에서 갈 수 있는 깊이까지 먼저 탐색하고 더 이상 갈곳이 없으면 되돌아 오는 방식이다.

DFS 는 자료구조 Stack을 사용한다 지난 글에서 다뤘듯이 Stack은 LIFO(Last In First Out) 후입선출 방식의 자료구조다.

그런데 왜 Stack을 사용할까?

DFS는 한 방향으로 깊게 탐색한 후 되돌아와야 할 경우가 있을시 돌아오는 방식이기 때문에 마지막에 방문한 노드를 기억했다가 다시 돌아와야 한다. 즉 DFS는 가장 최근에 탐색한 노드를 기억해야 한다는 뜻이다 그렇기 때문에 후입선출의 Stack이 필요한것이다.

그런데 DFS는 굳이 자료구조를 사용하지 않고 재귀함수로도 구현할 수 있는데 왜일까?
그 이유는 재귀 함수도 스택 구조를 사용하기 때문이다. 함수가 호출하면 현재 상태가 저장되고, 호출이 끝나면 이전 상태로 돌아가기 때문이다.

이번 역시 DFS도 가이드라인이 될만한 코드를 봐보자

우선 첫번째는 재귀함수를 이용한 방법이다.

public class DFS_Example {
    public static void dfs(List<Integer>[] graph, boolean[] visited, int node) {
        visited[node] = true;
        System.out.print(node + " ");  // 방문한 노드 출력

        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(graph, visited, next); // 재귀 호출
            }
        }
    }
}

방문한 노드를 visited 배열에 체크하고 출력하는 코드다

현재 노드에서 연결된 next 노드를 하나씩 방문하면서 재귀 호출하고 더이상 방문할 곳이 없으면 자동으로 이전 노드로 돌아간다.

흐름을 예로 들자면

dfs(1) → dfs(2) → dfs(4) (더 이상 갈 곳 없음) → 돌아감
dfs(2) → dfs(5) (더 이상 갈 곳 없음) → 돌아감
dfs(1) → dfs(3) → dfs(6) (더 이상 갈 곳 없음) → 종료

이런 느낌일 것이다.

 

두번째는 스택을 이용한 방법이다.

BFS의 큐를 이용한 방법과 굉장히 유사하지 않는가? 크기가 작은 노드부터 방문해야한다 등의 조건이 없는 이상 단순히

BFS의 코드에서 자료구조 Queue 를 Stack으로 바꾸면 끝이다. 물론 스택에서 꺼내는 순서에 따라 탐색 순서가 달라질 수 있으므로 주의해야 한다.

public class DFS_Stack {
    public static void dfs(List<Integer>[] graph, int start) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.length];

        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop(); // 가장 마지막에 들어온 노드 꺼내기

            if (!visited[node]) {
                visited[node] = true;
                System.out.print(node + " ");  // 방문한 노드 출력

               
                for (int next : graph[node]) {
                    if (!visited[next]) {
                        stack.push(next);
                    }
                }
            }
        }
    }
}

 

	재귀 DFS	스택 DFS
코드 가독성	간결하고 직관적	다소 길어질 수 있음
스택 사용 여부	X	O
재귀 호출 제한	재귀 호출 깊이 제한 존재	제한 없음
탐색 순서	DFS 원칙대로 탐색	스택에 넣는 순서에 따라 다를 수 있음
호출 방식	dfs(다음 노드) 호출	stack.push(다음 노드) 후 stack.pop()

 

두 방식의 차이점이라면 이렇게 설명 할 수 있다 하지만 개인적으로 특별한 조건이 없는 이상 BFS의 코드에서 Queue를 Stack으로 바꾸면 되기만 하면 되는데 굳이 재귀를 써야할지는 잘 모르겠다. 

 

우선 이렇게 BFS/DFS 두 방식을 모두 설명했는데 BFS는 가까운 노드 부터 방문하기 때문에 최단거리, 최소시간 등에서 사용하면 유리하고 완전 탐색이 필요한 경우 DFS가 유리 할 것이다. 물론 두 방식으로 풀 수 있는 문제가 존재하는데 개인적으로 BFS가 더 익숙하기도 하고 더 쉽다고 느껴져 BFS를 애용하는 편이다. 또한 문제를 엄청 많이 풀어본건 아니지만 대부분의 경우 최단거리, 최소 시간을 구하는 경우가 많기도 했다.

 

마지막으로 BFS와 DFS의 차이점을 정리한 표를 보고 마치자

	BFS	DFS
탐색 방식	가까운 노드부터 탐색	한쪽 방향으로 깊게 탐색
사용 자료구조	Queue (FIFO)	Stack (LIFO) 또는 재귀함수
탐색 특징	최단 거리 탐색에 유리	모든 경우의 수 탐색
주로 사용되는 문제 유형	최단거리, 미로 탐색, 네트워크 연결	백트래킹, 그래프 연결 요소 찾기

 

 

참고한 블로그 및 사진 출처

https://foameraserblue.tistory.com/188

PS를 하며 느끼는 DFS와 BFS 선택의 기준