DFS와 BFS

김준호·2020년 7월 20일
BFSDFSalgorithm깊이 우선 탐색너비 우선 탐색
1

알고리즘

목록 보기
5/7
post-thumbnail
post-custom-banner

그래프 이론을 통해서 그래프에서 사용되어지는 용어들을 알아봤다. 이제 모든 자료구조의 기초가 되는 탐색 연산을 알아볼 차례인데, DFS와 BFS로 두가지 연산이 존재한다.

DFS

깊이 우선 탐색(Depth-First-Search)는 너비 우선 탐색과 달리 탐색 방향이 아래로 진행된다. 어느정도 접해본 사람이라면 쉽게 이해가 가능하지만 처음 접하는 사람에게는 아래로 진행되는 것과 BFS의 사이드로 진행되는 것의 차이를 알아채기 쉽지 않다.

기본적으로 DFS는 Stack이라고 생각해도 무방하다. 보통 DFS는 재귀 함수를 이용해서 구현되는데 재귀의 특성상 그 순간의 관련된 부분들을 탐색하는것이 아니라 한번 탐색하고 재귀 호출이 발생이되면 탐색한 부분을 제외한 나머지 부분을 처음부터 탐색한다. 즉, 이전에 탐색했던 것들을 무시하고 한 방향으로 진행한다.

위의 그림처럼 순서대로 아래로 진행이되는데, 만약 1,2,3,4가 모두 순서대로 방문된 시점이라고 가정해보자. 이 때, 4가 방문되는 순간 또다시 재귀 호출이 이루어지게 되는데 이제 더이상 아래로 방문할 곳이 없기때문에 함수가 종료된다. 그렇게 쌓여있던 함수들이 반복적으로 종료되어서 2번 정점을 호출했던 함수까지 오게된다. 이 때, 2번정점을 호출했던 함수는 1번 정점으로 앞서 함수들이 종료되었던과는 달리 5번을 호출할 수 있기때문에 호출한다.

즉, 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 돌아가서 탐색을 수행하는 방식으로 이와같은 알고리즘을 DFS라고 한다.

구현

public class graphDFS {
  private List<Integer>[] adj;
  private boolean visited[];
  private int nodeSize;

  private graphDFS(int size) {
    nodeSize = size;
    adj = new List[size];
    visited = new boolean[size];
    for(int i = 0; i < size; ++i) {
      adj[i] = new ArrayList<>();
    }
  }
  ...

DFS 클래스를 만들어 보면 adj는 간선(Edge)리스트를 저장하기위한 맴버변수다. 이 때, 인접리스트를 사용한 것인데 인접 행렬을 통해서 구할 수 있다.

인접 행렬 같은 경우 2차원 배열을 이용해서 i -> j로 이동 할 수 있다는 것을 표현할 때 adj[i][j] = true와 같이 표현해서 간선정보를 저장하는 방법이다.

visited 배열은 '그 정점(vertex)에 방문했는가'에 대한 정보를 담는 맴버 변수다. 만약 방문처리를 하지않는다면 무한루프의 늪에 빠질것이다.

그리고 마지막으로 nodeSize는 사실 문제를 접할 때는 문제에 명시되어있거나 하지만, 여기에서는 명시적으로 주었다.

private void addEdge(int u, int v) { 
    adj[u].add(v);
    adj[v].add(u);
  }

간선의 정보를 양쪽에 전달함으로 무방향 그래프를 만들었다.

private int getComponents() {
    int compo = 0;

    for(int i = 0; i < nodeSize; ++i) {
      if(!visited[i]) {
        compo++;
        System.out.println("-- new component --");
        DFS(i);
      }
    }
    return compo;
  }

메소드 getComponents()는 사실상 모든 노드를 탐색하는 함수다. 이과정에서 컴포넌트의 개수를 구할 수 있다..

반목문을 통해서 모든 정점을 조회하면서 방문하지 않은 정점에 대해서만 깊이 우선 탐색을 하고 있다. 즉, DFS()를 통해서 방문한 정점에 대해서는 다시 방문하지 않는 것이다.

여기서 만약 모든 노드가 이어져있다면 DFS()를 한번 호출하겠지만 여러 컴포넌트라면 컴포넌트의 개수만큼 호출이 된다.

  private void DFS(int curr) {
    System.out.println("curr : " + curr);
    visited[curr] = true;

    for(int next : adj[curr]) {
      if(!visited[next]) {
        DFS(next);
      }
    }
  }

DFS() 메소드로 넘어오는 파라미터는 처음 방문할 노드의 번호다. curr째 정점부터 시작해서 같은 컴포넌트에 있는 모든 노드들을 깊이 우선으로 탐색하게 된다.

이 때, DFS 메소드를 재귀호출 하고 있다. 재귀함수는 하나의 Stack의 역할을 한다. FILO(First-In-Last-Out)의 특성을 가지고 있다. 즉, 방문하는 노드를 계속 push하고 마지막으로 방문한 노드부터 pop하면서 깊이가 가장 깊은 노드부터 탐색하고 있다.

그리고 같은 컴포넌트의 노드들을 탐색하는 원리는 위에서 설정해준 간선 정보를 담은 인접리스트를 이용하기 때문이다. 즉 서로 이어져 있는 정점에 대해서만 탐색을 진행하게 된다.

방문처리에 대해서 이야기 해보자면 항상 방문하는 노드를 바로바로 처리해줘야한다는 것을 명심해야한다.

테스트

graphDFS g = new graphDFS(10);

g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);

g.addEdge(5, 6);
g.addEdge(5, 7);
g.addEdge(5, 8);
g.addEdge(8, 9);

int component = g.getComponents();

System.out.println("coponent size : " + component);

결과 :

-- new component --
curr : 0
curr : 2
curr : 4
curr : 3
curr : 1
-- new component --
curr : 5
curr : 6
curr : 7
curr : 8
curr : 9
coponent size : 2

BFS

너비 우선 탐색(BFS, Breadth-First-Search)은 DFS와 달리 탐색 한 순간의 정점과 이웃한 정점들을 탐색하는 알고리즘이다. 깊이 우선 탐색보다는 익숙한 이 알고리즘은 보통 주변 탐색이라는 말로 설명이 가능하다. 즉 시작하는 정점에서 이웃하는 모든 정점을 방문하고 방문한 정점들의 이웃 정점들을 모두 방문하는 식으로 진행된다.

DFS는 스택이라고 봐도 무방하다고 했다. 반대로 BFS는 큐로 구현되어진다. 큐의 특성을 이해한다면 왜 BFS가 큐를 사용하는지 알 수 있다. BFS는 방문했던 노드들을 순서대로 탐색하기 때문에 FIFO가 적절하다.

구현

public class graphBFS {
  private List<Integer>[] adj;
  private boolean visited[];
  private int nodeSize;

  private graphBFS(int size) {
    nodeSize = size;
    adj = new List[size];
    visited = new boolean[size];
    for(int i = 0; i < size; ++i) {
      adj[i] = new ArrayList<>();
    }
  }
  ...

기본적인 틀은 앞서 그래프를 구현하는것이기 때문에 DFS와 같은 이유로 같은 구현이다.

private void addEdge(int u, int v) { 
    adj[u].add(v);
    adj[v].add(u);
  }

간선의 정보를 양쪽에 전달함으로 무방향 그래프를 만들었다.

private int getComponents() {
    int compo = 0;

    for(int i = 0; i < nodeSize; ++i) {
      if(!visited[i]) {
        compo++;
        System.out.println("-- new component --");
        BFS(i);
      }
    }
    return compo;
  }

메소드 getComponents()는 사실상 모든 노드를 탐색하는 함수다. 이과정에서 컴포넌트의 개수를 구할 수 있다.

반목문을 통해서 모든 정점을 조회하면서 방문하지 않은 정점에 대해서만 너비 우선 탐색을 하고 있다. 즉, BFS()를 통해서 방문한 정점에 대해서는 다시 방문하지 않는것이다.

여기서 만약 모든 노드가 이어져있다면 BFS()를 한번 호출하겠지만 여러 컴포넌트라면 컴포넌트의 개수만큼 호출이 된다.

  private void BFS(int start) {
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;
    q.offer(start);

    while(q.size() != 0) {
      int curr = q.poll();
      System.out.println("visit : " + curr);
      for(int next : adj[curr]) {
        if(visited[next]) continue;
        visited[next] = true;
        q.offer(next);
      }
    }

BFS() 메소드로 넘어오는 파라미터는 처음 방문할 노드의 번호다. start째 정점부터 시작해서 같은 컴포넌트에 있는 모든 노드들을 너비 우선으로 탐색하게 된다.

이 때, 자료구조 큐를 사용한다. 큐의 특성을 생각해보면 FIFO(First-In-First-Out)의 성질이 있다. 즉, 방문한 노드부터 순차적으로 탐색한다는 것을 알 수 있다. 따라서 인접한 정점에 대해서 먼저 탐색한다.

그리고 같은 컴포넌트의 노드들을 탐색하는 원리는 위에서 설정해준 간선 정보를 담은 인접리스트를 이용하기 때문이다. 즉 서로 이어져 있는 정점에 대해서만 탐색을 진행하게 된다.

테스트

graphBFS g = new graphBFS(10);

g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);

g.addEdge(5, 6);
g.addEdge(5, 7);
g.addEdge(5, 8);
g.addEdge(8, 9);

int component = g.getComponents();

System.out.println("coponent size : " + component);

결과 :

-- new component --
visit : 0
visit : 2
visit : 4
visit : 3
visit : 1
-- new component --
visit : 5
visit : 6
visit : 7
visit : 8
visit : 9
coponent size : 2

시간복잡도

DFS와 BFS의 수행시간은 탐색이 각 정점을 한 번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에 O(V + E)다. 여기서 V는 정점의 수이고 E는 간선의 수이다.

다만 두 탐색방법의 차이점은 정점 방문시기와 간선 사용 순서가 다른것일 뿐이다.

profile
김준호
https://junhok82.github.io/
이전 포스트

허프만 코딩(Huffman coding)

다음 포스트

KMP 알고리즘

post-custom-banner

0개의 댓글