[코딩테스트 대비] DFS, BFS 정리

DFS, BFS 정리

---

DFS, BFS는 그래프에 속하는 알고리즘이다. 코딩테스트에서 경로를 찾는 문제에서 많이 출제가 된다.

DFS

Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

Stack 혹은 재귀함수(Recursion)으로 구현된다.

• 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
• 모든 노드를 방문하는 경우에 이 방법을 사용한다.

시간 복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V^2)

접점(V), 간선(E)

Java Code

/* 인접 리스트 이용 */
class Graph {
  private int V;
  private LinkedList<Integer> adj[];
 
  Graph(int v) {
      V = v;
      adj = new LinkedList[v];
      // 인접 리스트 초기화
      for (int i=0; i<v; ++i)
          adj[i] = new LinkedList();
  }
  void addEdge(int v, int w) { adj[v].add(w); }
 
  /* DFS에 의해 사용되는 함수 */
  void DFSUtil(int v, boolean visited[]) {
      // 현재 노드를 방문한 것으로 표시하고 값을 출력
      visited[v] = true;
      System.out.print(v + " ");
 
      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> it = adj[v].listIterator();
      while (it.hasNext()) {
          int n = it.next();
          // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
          if (!visited[n])
              DFSUtil(n, visited);
      }
  }
 
  /* DFS */
  void DFS(int v) {
      boolean visited[] = new boolean[V];
 
      // v를 시작 노드로 DFSUtil 재귀 호출
      DFSUtil(v, visited);
  }
}

연관 문제

DFS와 BFS : https://developer-mac.tistory.com/63

연결 요소 : https://www.acmicpc.net/problem/11724

이분 그래프 : https://www.acmicpc.net/problem/1707

섬의 개수 : https://developer-mac.tistory.com/66

단지번호붙이기 : https://www.acmicpc.net/problem/2667

섬의 개수 : https://www.acmicpc.net/problem/4963

위 문제들은 DFS, BFS의 기본을 이용하는 문제이므로 개념을 익히기에 좋다. DFS, BFS 두개다 해보는 것을 추천한다.

BFS

Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.

Queue를 사용해서 구현한다.

시간 복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V^2)

접점(V), 간선(E)

Java Code

class Graph {
  private int V;
  private LinkedList<Integer> adj[];
 
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i)
      adj[i] = new LinkedList();
  }
 
  void addEdge(int v, int w) { adj[v].add(w); }
 
  /* BFS */
  void BFS(int s) {
    boolean visited[] = new boolean[V];
    LinkedList<Integer> queue = new LinkedList<Integer>();
 
    visited[s] = true;
    queue.add(s);
 
    while (queue.size() != 0) {
      // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
      s = queue.poll();
      System.out.print(s + " ");
 
      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

추가적으로 BFS로 효과적으로 풀 수 있는 문제들이 있다.

3가지의 조건을 만족한다.

1. 최소 비용 문제

2. 간선의 가중치가 1이다.

3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)

연관 문제

토마토1 : https://developer-mac.tistory.com/67

토마토2 : https://developer-mac.tistory.com/68

토마토 문제에서 BFS를 이용해 푸는 것을 연습할 수 있다. 두 문제의 차이는 배열의 차원이다. 첫 번째 토마토 문제는 2차원 배열을 이용하고, 2번째 문제는 3차원 배열을 이용한다. 차례대로 풀어보는 것을 추천한다.

참고자료

DFS - GeeksforGeeks : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

BFS - GeeksforGeeks : https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/