😇 DFS, BFS in Java

알고리즘 문제에서 제일 기초가 되는 DFS, BFS!!!
풀 때마다 헷갈리는 부분 중 하나인데요. 확실하게 기억하고 싶어서 정리해봅니다. 🥲

먼저, 아래의 강의를 참고했습니다. 유튜브에서 DFS, BFS in Java 라고 치면 제일 먼저 나오는 강의입니다.

🔗 Graph DFS, BFS in Java

---

DFS (Depth First Search)

DFS는 자신과 연결된 노드부터 탐색하는 알고리즘입니다. 후입 선출 방식으로 구현합니다. 미흡한 그림 실력으로 DFS를 트리형태로 나타내본다면!

이러한 순서로 방문을 합니다.

• 제일 상위의 노드를 1번으로 가정했을 때 자식 노드부터 방문을 합니다.
• 방문한 노드의 자식 노드를 방문합니다.
  • 1번을 stack에 넣습니다.
  • 1번을 뽑아 출력합니다.
  • 1번과 연결된 4, 3, 2를 순서대로 넣습니다.
  • stack에 있는 2번을 뽑아 출력합니다.
  • 2번과 연결된 6, 5를 순서대로 넣습니다.
  • stack에 넣고 뽑고 출력하는 작업을 반복합니다.
• recursion(재귀) 통해 쉽게 구현할 수 있습니다.

코드 구현 (in Java)

   public static void dfs(int node, boolean[] visited, StringBuilder sb) {
        if(visited[node]) return;
        
        visited[node] = true;
        sb.append(node + " ");
        for(int nextNode:nodeList[node]) {
            dfs(nextNode, visited, sb);
        }
    }

---

BFS (Breadth First Search)

BFS는 형제 노드를 먼저 탐색하는 알고리즘입니다. 선입선출 방식인 queue로 구현합니다. BFS를 트리형태로 나타내본다면!

이러한 순서로 방문을 합니다.

• 제일 상위의 노드를 1번으로 가정했을 때 형제 노드부터 방문 합니다.
  • 1번을 queue에 넣습니다.
  • 1번을 뽑아 출력합니다.
  • 1번과 연결된 2, 3, 4를 순서대로 넣습니다.
  • queue에 있는 2번을 뽑아 출력합니다.
  • 2번과 연결된 5, 6를 순서대로 넣습니다.
  • 선입선출이기 때문에 3번을 뽑아 출력합니다.
  • 3번과 연결된 7, 8을 넣습니다.
  • 4번을 뽑아 출력하고 연결된 9, 10을 넣습니다.
  • queue가 빌 때까지 반복합니다.

코드 구현 (in Java)

public static void bfs(int node, boolean[] visited, StringBuilder sb) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(node);
        
        while(!queue.isEmpty()) {
            node = queue.poll();
            
            if(visited[node]) continue;
            
            visited[node] = true;
            sb.append(node + " ");
            
            for(int nextNode:nodeList[node]) {
                queue.add(nextNode);
            }
        }
    }

---

💡 정리 후 느낀점

• 그래프와 트리에 대한 이해가 필요함을 느껴 조만간 정리할 예정입니다.