본문 바로가기
Algorithm & Data Structure

그래프 탐색 완벽 가이드: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

하얀종이개발자 2024. 8. 27. 03:22
안녕하세요, 스터디 6주 차입니다. 그래프에 대해 알아보고, 그래프를 탐색하는 방법 중 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 이야기해보겠습니다. 그래프 자료구조와 탐색 방법은 코딩테스트에서 가장 중요한 빈도로 출제를 차지하고 있죠. 도움이 되었으면 좋겠습니다. 같이 시작해 보시죠 😊

1. 그래프(Graph) 자료구조가 뭐야?

그래프 자료구조

 
그래프(Graph)는 정점(Vertex)와 Edge(간선)로 구성된 비선형 자료구조를 말합니다.
정점은 데이터를 나타내고, 간선은 정점 간의 관계를 표현합니다. 이를 통해 다차원적인 데이터를 효율적으로 표현할 수 있죠.
그래프는 현실 세계의 복잡한 관계를 모델링할 때 유용한 구조입니다. 예를 들어, 지도에서 도시 간의 거리를 나타내거나 소셜 네트워크의 친구 관계 등을 그래프로 표현할 수 있습니다.
 

1.1. 트리와 그래프의 관계

이전에 포스팅한 트리 자료구조에 대해여... 내용 보셨다면 비슷하다고 느끼실 수 있습니다. 트리(Tree) 자료구조가 뭐였죠? 복습을 해볼까요? 트리(Tree)는 그래프의 일종으로, 노드와 간선으로 이루어진 계층적 방향 그래프!! (부모 자식 관계)
말 그대로 그래프가 좀 더 큰 개념으로 그래프의 일종인 트리는 계층적 구조를 가지며, 루트 노드를 중심으로 모든 노드가 연결되고 사이클이 없는 방향 그래프입니다. 즉, 트리는 그래프 중에서 계층적 구조와 방향성을 가진 특별한 그래프라고 생각할 수 있습니다.
 

1.2. 그래프의 종류

그래프는 다양한 형태로 분류됩니다.
 

무방향 그래프와 방향 또는 양방향 그래프

무방향그래프와 방향그래프

  • 무방향 그래프는 정점 간의 간선이 연결되어 있을 뿐, 방향을 가지지 않은 그래프를 말합니다.
  • 방향 그래프는 간선이 특정한 방향을 가지는 그래프를 말합니다. 한쪽 방향만 있을 수도 있고 양쪽방향을 가질 수도 있습니다.

 
 

가중치가 없는 그래프와 있는 그래프

가중치가 없는 그래프와 있는그래프

  • 가중치가 없는 그래프는 말그대로 간선에 가중치가 없는 그래프입니다. 간선이 단순히 정점들을 연결할 뿐, 비용이나 거리는 고려되지 않습니다.
  • 가중치가 있는 그래프는 간선마다 특정 가중치(비용 또는 거리)가 부여되어 추가적인 정보를 표현할 수 있습니다.

 

사이클이 없는 방향 그래프와 있는 그래프

사이클이 없는 그래프와 있는 그래프

 

  • 사이클이 없는 그래프는 방향을 가진 간선들이 존재하지만, 어떠한 시작 정점에서 출발하면 다시 그 시작정점으로 돌아오는 경로가 없는 그래프입니다. 흔히 DAG라고 줄여서 표현합니다. 주로 위상 정렬(Topological Sort)에 사용합니다.
  • 사이클이 있는 그래프는 간선에 방향이 있고, 사이클(정점에서 출발해 다시 그 정점으로 돌아오는 경로)이 존재하는 그래프를 말합니다.

 

2. 그래프를 저장하는 방법

컴퓨터 시스템에는 그래프를 저장하는 방법이 여러 가지 존재하는데, 이론적으로 행렬과 리스트 구조중의 하나로 구현이 가능합니다.
실제 어떻게 저장하고 사용하게 되는지 알아보겠습니다. 편의상 이제 정점(Vertex)를 노드라고 지칭하겠습니다.
 

2.1. 그래프 구현(인접행렬)

인접 행렬은 2차원 배열을 사용해 그래프의 정점 간 연결 관계를 나타냅니다. 행과 열의 인덱스가 각 노드를 가리키고, 배열의 값은 간선의 존재 유무 혹은 가중치를 의미합니다. 다만, 노드 대비 간선이 적은 경우 메모리 공간의 효율이 좋지 못한 단점이 있습니다.
 

인접행렬로 구현된 그래프 표현방식

1. 노드의 개수 * 노드의 개수 만큼 2차원 배열로 행렬을 만듦
2. 행은 시작노드, 열은 연결된 노드를 의미하고, 배열의 값은 가중치로 표현함
 

인접행렬로 표현한 그래프

  • 가중치가 없는 간선을 나타내는 경우 간선이 있으면 1, 없으면 0으로 표기할 수도 있습니다.
  • 노드가 100개이고 간선이 1개인 경우에도 100X100의 행렬이 필요하므로 메모리 낭비가 될 수 있습니다.
  • 특정노드 사이 간선 존재 여부를 한 번에 알 수 있기 때문에 간선을 찾는 경우가 많으면 인접행렬로 구현할 수 있습니다.

 

2.2. 그래프 구현(인접리스트)

특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결해서 표현하는 방법입니다. 실제 그래프의 노드 개수만큼만 추가하므로 메모리의 낭비가 없는 장점이 있으며, 드문 케이스이지만 특정노드에 모든 노드가 연결된 경우에는 탐색 시 모두 탐색하는 O(N)의 성능을 보일 수 있습니다.
 

인접리스트로 구현된 그래프 표현방식

1. 노드 개수만큼 배열을 준비
2. 각 배열의 인덱스는 시작노드를 나타냄, 해당 인덱스에 연결된 노드를 리스트에 계속 추가함

인접리스트로 표현한 그래프

 

3. 인접 행렬 VS 인접 리스트

두 표현방식을 표로 비교해 보겠습니다. (V는 정점의 수, E는 간선의 수)

  공간복잡도 특정 정점의 간선을 찾는 경우 그래프의 모든 간선을 찾는 경우
인접 행렬 O(V^2) O(1) O(V^2)
인접 리스트 O(V+E) O(E) 또는 O(E/V)이 대부분 O(V+E)

 
인접행렬은 특정 정점의 간선을 찾는 경우 많으면 유리하지만, 메모리를 많이 쓰게 되는 단점이 있습니다.
만약 노드의 개수가 많다면, 메모리 초과의 가능성이 있는 인접행렬보다 인접리스트가 유리하겠죠. 그래서 특정 정점의 간선을 찾는 경우가 많을 때를 제외하면 대부분 인접리스트로 구현하는 게 유리합니다. (뭘 써야 할지 모르면 인접리스트로 구현)

 

4. 그래프 탐색 방법: DFS vs BFS

그래프는 규칙이 명확하지 않고 좀 더 큰 개념이어서 탐색이 복잡합니다. 그래프의 모든 정점을 탐색하는 알고리즘인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이라는 두 가지 주요 탐색 방법을 통해 정해진 순서대로 순회할 수 있습니다.
 

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

DFS

 
깊이우선탐색(DFS)은 시작 노드의 인접 정점 중 하나를 더 이상 탐색할 노드가 없을때까지 깊이 탐색하고, 더이상 탐색할 노드가 없으면 최근에 방문했던 노드로 퇴각 후 나머지 인접 노드도 같은 방식으로 탐색하는 알고리즘입니다.

 

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

BFS

 
너비우선탐색(BFS)은 현재 위치에서 간선이 1개인 가장 가까운 노드들부터 모두 방문하고 다음 노드로 이동하여 탐색하는 알고리즘입니다. 시작 노드를 기준으로 넓게 퍼지게 탐색한다고 하여 너비 우선 탐색이라고 이름 붙여졌습니다.

 

5. 그러면 깊이우선탐색(DFS)에 필요한 것은?

  • 가능한 한 깊이 탐색할 수 있어야 함
  • 더 이상 깊은 곳이 없는 경우 가장 최근에 방문했던 노드로 퇴각해야 함
  • 이미 방문한 노드는 중복해서 방문하지 않아야 함

가장 최근에 방문했던 노드로 가는 효율적인 방법은 뭐가 있을까?

  • LIFO (Last In First Out)로 동작하는 스택을 활용할 수 있음
  • 방문할 노드는 PUSH, 방문한 노드는 POP 하면 스택의 TOP은 가장 최근에 방문한 노드를 가리킴
  • 함수의 Call Stack도 스택과 같이 동작하므로 재귀함수로 구현하는 경우가 많음
  • 방문 여부를 기록하는 visited 배열을 활용하여 방문하지 않은 노드만 방문할 수 있음

 

5.1. DFS 완벽 동작가이드

깊이 우선 탐색(DFS)은 시작 정점에서 출발하여 가능한 한 깊이까지 내려간 후, 더 이상 갈 곳이 없으면 가장 마지막에 방문했던 정점으로 돌아와서 다른 경로를 탐색하는 방법입니다. DFS는 재귀 호출을 사용하여 구현될 수 있으며, 그래프의 경로 탐색, 사이클 검출, 등을 구하는 데 자주 사용될 수 있습니다.

  • 동작 방식: DFS는 스택(또는 재귀 호출의 콜 스택)을 사용하여 그래프를 탐색함. 한 번 방문한 노드는 다시 방문하지 않도록 처리하며, 끝까지 깊이 탐색한 후 다시 돌아오는 방식을 사용.

 

DFS 동작 예시 설명 (재귀)

그림을 그려 동작을 설명하겠습니다.

깊이우선탐색 동작원리1

  • DFS(A) 호출, 노드 A 방문 처리
    • DFS 탐색이 시작되며, 노드 A를 방문 처리.
  • DFS(A)에서 A와 연결된 노드 중 방문하지 않은 노드를 탐색, DFS(B) 호출
    • A와 연결된 아직 방문하지 않은 노드 B를 확인하고, DFS(B) 호출.
    • 노드 B 방문 처리.
    • 노드 A와 연결된 모든 노드를 아직 탐색하지 않았기 때문에 A는 스택에서 팝(pop)되지 않음.
  • DFS(B)에서 B와 연결된 노드 중 방문하지 않은 노드를 탐색, DFS(D) 호출
    • B와 연결된 아직 방문하지 않은 노드 D를 확인하고, DFS(D) 호출.
    • 노드 D 방문 처리.

깊이우선탐색 동작원리2

 
 

  • 현재 DFS(D)가 호출된 상황
    • D와 연결된 노드 중 방문하지 않은 노드가 없으므로 DFS(D)가 종료.
    • Call Stack에 의해 DFS(B)의 남은 부분이 호출됨.
  • DFS(B)에서 B와 연결된 노드 중 아직 방문하지 않은 노드 E 확인, DFS(E) 호출
    • B와 연결된 아직 방문하지 않은 노드 E를 확인하고 DFS(E)를 호출.
    • 노드 E 방문 처리.

 

깊이우선탐색 동작원리3

 

  • 현재 DFS(E)가 호출된 상황
    • E와 연결된 노드 중 방문하지 않은 노드가 없으므로 DFS(E)가 종료.
    • Call Stack에 의해 다시 DFS(B)의 남은 부분이 호출됨.
  • 현재 DFS(B)가 호출된 상황
    • B와 연결된 노드 중 더 이상 방문할 노드가 없으므로 DFS(B)가 종료.
    • Call Stack에 의해 DFS(A)의 남은 부분이 호출됨.

 

깊이우선탐색 동작원리3

 

  • 현재 DFS(A)가 호출된 상황
    • A와 연결된 노드 중 더 이상 방문할 노드가 없으므로 DFS(A)가 종료.
    • Call Stack에 의해 DFS(A)의 남은 부분이 호출됨.
  • DFS(A)에서 A와 연결된 아직 방문하지 않은 노드 C 확인, DFS(C) 호출
    • A와 연결된 노드 C를 확인하고 DFS(C) 호출.
    • 노드 C 방문 처리.
  • 현재 DFS(C)가 호출된 상황
    • C와 연결된 노드 중 더 이상 방문할 노드가 없으므로 DFS(C)가 종료.
    • Call Stack에 의해 다시 DFS(A)의 남은 부분이 호출됨.
  • 더 이상 방문할 노드가 없으므로 DFS 전체 종료

 

5.2. 자바 코드로 구현한 DFS

public class DFS {

  // 전역 인접 리스트 및 방문 리스트
  static List<List<Integer>> adj = new ArrayList<>();
  static boolean[] visited;

  // 그래프에 간선을 추가하는 함수
  // 인자: v (정점), w (연결된 정점)
  public static void addEdge(int v, int w) {
    adj.get(v).add(w); // 정점 v의 인접 리스트에 정점 w를 추가
  }

  // 깊이 우선 탐색(DFS)을 수행하는 함수
  // 인자: v (현재 정점)
  public static void dfs(int v) {
    // 현재 정점을 방문했다고 표시하고 출력
    visited[v] = true;
    System.out.print(v + " ");

    // 현재 정점에 인접한 모든 정점을 순회
    for (int i : adj.get(v)) {
      if (!visited[i]) {
        dfs(i);
      }
    }
  }

  // 메인 함수: 그래프 생성 및 DFS 수행
  public static void main(String[] args) {
    // 정점의 개수
    int V = 5;
    visited = new boolean[V];

    // 인접 리스트 초기화
    for (int i = 0; i < V; i++) {
      adj.add(new ArrayList<>());
    }

    // 그래프에 간선 추가 (주어진 다이어그램에 따라)
    addEdge(0, 1); // A -> B
    addEdge(0, 2); // A -> C
    addEdge(1, 3); // B -> D
    addEdge(1, 4); // B -> E

    System.out.println("깊이 우선 탐색 (정점 0에서 시작):");

    // DFS 수행 (정점 0부터 시작)
    dfs(0);
  }
}

 

6. 그러면 너비우선탐색(BFS)에 필요한 것은?

  • 루트 노드부터 시작해서, 가장 가까운 노드들부터 방문할 수 있어야 함
  • 가까운 노드를 모두 탐색(1개의 간선으로 갈 수 있는 노드)하면 그다음 가까운 노드로 넘어가야 함

가장 가까운 노드부터 방문하는 효율적인 방법은 뭐가 있을까?

  • FIFO (First In First Out)로 동작하는 큐를 활용할 수 있음
  • 시작노드를 방문했다고 기록하고 큐에 PUSH
  • 큐의 첫 번째 노드를 POP 하고 POP 한 노드와 인접하게 연결된 노드 중 방문하지 않은 노드를 방문했다고 기록하고 큐에 모두 PUSH
    => 모든 노드를 방문할 때까지 반복

 

6.1. BFS 완벽 동작가이드

 
너비 우선 탐색(BFS)은 시작 정점에서 출발하여 인접한 모든 정점을 먼저 탐색한 후, 그다음 깊이로 내려가는 방식입니다. BFS는 큐를 사용하여 구현하며, 최단 경로 탐색에서 매우 유용합니다.

  • 동작 방식: BFS는 큐를 사용하여 탐색할 정점을 차례로 저장하고, 한 번 방문한 정점을 다시 큐에 넣지 않도록 함. 또한 BFS는 그래프에서 최단 경로를 찾거나 레벨별 탐색을 할 때 효과적

 

BFS 동작 예시 설명 (큐)

그림을 그려 동작을 설명하겠습니다.

너비우선탐색 동작원리1

  • 노드 A를 방문, 큐에 PUSH
    • 시작 노드 A를 방문하고 큐에 삽입.
  • 큐에서 가장 위에 있는 노드 A를 POLL
    • A를 큐에서 꺼내고, A에서 방문하지 않은 가장 가까운 노드 B, C를 방문하고 큐에 삽입.

너비우선탐색 동작원리1

큐에서 가장 위에 있는 노드 B를 POLL

  • B를 큐에서 꺼내고, B에서 방문하지 않은 가장 가까운 노드 D, E를 방문하고 큐에 삽입.

 

너비우선탐색 동작원리2

 

  • 큐에서 가장 위에 있는 노드 C를 POLL
    • C를 큐에서 꺼내고, C에서 방문하지 않고 인접한 노드가 없으므로 처리 종료.
  • 큐에서 가장 위에 있는 노드 D를 POLL
    • D를 큐에서 꺼내고, D에서 방문하지 않고 인접한 노드가 없으므로 처리 종료.
  • 큐에서 가장 위에 있는 노드 E를 POLL
    • E를 큐에서 꺼내고, E에서 방문하지 않고 인접한 노드가 없으므로 처리 종료.
  • 모든 노드를 방문했으므로 탐색 종료
    • 큐가 비었으므로 모든 노드를 방문했으며, 탐색을 종료.

 

6.2. 자바 코드로 구현한 BFS

public class BFS {

  // 전역 인접 리스트 및 방문 리스트
  static List<List<Integer>> adj = new ArrayList<>();
  static boolean[] visited;

  // 그래프에 간선을 추가하는 함수
  // 인자: u (정점), v (연결된 정점)
  public static void addEdge(int u, int v) {
    adj.get(u).add(v); // 정점 u의 인접 리스트에 정점 v를 추가
  }

  // 너비 우선 탐색(BFS)을 수행하는 함수
  // 인자: start (시작 정점)
  public static void bfs(int start) {
    ArrayDeque<Integer> q = new ArrayDeque<>();
    visited[start] = true;
    q.addLast(start);

    while (!q.isEmpty()) {
      int v = q.pollFirst(); // 큐에서 첫 번째 정점을 꺼냄
      System.out.print(v + " ");

      // 현재 정점에 인접한 모든 정점을 순회
      for (int i : adj.get(v)) {
        if (!visited[i]) {
          visited[i] = true;
          q.addLast(i); // 방문하지 않은 인접 정점을 큐에 추가
        }
      }
    }
  }

  // 메인 함수: 그래프 생성 및 BFS 수행
  public static void main(String[] args) {
    // 정점의 개수
    int V = 5;
    visited = new boolean[V];

    // 인접 리스트 초기화
    for (int i = 0; i < V; i++) {
      adj.add(new ArrayList<>());
    }

    // 그래프에 간선 추가 (주어진 다이어그램에 따라)
    addEdge(0, 1); // A -> B
    addEdge(0, 2); // A -> C
    addEdge(1, 3); // B -> D
    addEdge(1, 4); // B -> E

    System.out.println("너비 우선 탐색 (정점 0에서 시작):");

    // BFS 수행 (정점 0부터 시작)
    bfs(0);
  }
}

 

7. 깊이우선탐색(DFS) VS 너비우선탐색(BFS)

  DFS BFS
탐색 방식 최대한 깊이 탐색한 후 백트래킹 가장 가까운 노드부터 차례로 탐색
구현 방식 스택 또는 재귀 사용 큐 사용
적합한 문제 백트래킹 및 조합 문제 최단 경로 탐색 문제
메모리 사용   DFS보다 많음

 
깊이 우선 탐색(DFS)은 한 경로를 끝까지 탐색한 후, 이전에 방문한 지점으로 되돌아와 다른 경로를 탐색하는 백트래킹 방식이 특징입니다. 이 방식은 결정을 내린 후 그 결정을 바탕으로 가능한 모든 경로를 탐색하는 데 유리하다는 것을 알고 계시면 좋습니다.
 
특징

  • 재귀적인 탐색 과정에서 깊이 있는 경로를 우선 탐색.
  • 백트래킹을 통해 다른 경로를 다시 탐색.
  • 백트래킹을 통해 가능한 경로를 모두 탐색해야 할 때 효과적.

적용에 적합한 코딩테스트 문제

  • 퍼즐 문제: 스도쿠처럼 가능한 모든 해를 탐색하는 문제.
  • 조합 문제: 예를 들어, 1부터 5까지 숫자를 사용해 합이 10이 되는 모든 조합을 찾는 문제.
  • 백트래킹 문제: 경로를 되돌아가며 다른 해를 찾을 수 있는 문제들에 적합.

 
너비 우선 탐색(BFS)은 시작 노드에서 가까운 노드부터 차례대로 탐색하기 때문에 최단 경로를 찾는 데 최적화되어 있습니다. 이 알고리즘은 최적해를 보장하므로, 탐색에서 가장 적은 단계로 원하는 목표에 도달할 때 유리합니다.
 
특징

  • 큐를 사용하여 시작점에서 가까운 노드부터 차례로 탐색. (깊이 우선 탐색보다 메모리 사용량이 높음)
  • 탐색 과정에서 각 단계별로 인접한 노드를 먼저 처리하여 최단 경로를 보장.

적용에 코딩테스트 문제

  • 미로 찾기: 시작점에서 목표 지점까지 가장 짧은 경로를 찾는 문제.
  • 최단 경로 문제: 주어진 조건에서 가장 적은 단계를 통해 목적지에 도달해야 하는 문제에 적합.
  • 네트워크 탐색: 가까운 노드부터 탐색하는 것이 중요한 상황에서 유리.

 

물론 둘 다 되는 경우가 존재하기 때문에 애매하면 메모리 사용량이 덜 드는 깊이 우선 탐색(DFS)을 먼저 고려해 보면 좋을 것 같네요.

 

그래프 자료구조와 그래프 탐색알고리즘 중에 깊이우선탐색(DFS), 너비우선탐색(BFS)에 대해서 정리해봤습니다.
사실 현실에서 많이 보이는 그래프 알고리즘은 최단 경로 알고리즘인 다익스트라, A*, 벨만-포드, 플로이드 알고리즘 등이 있습니다. 네트워크 설계, 교통시스템, 길 찾기 등등에 말이죠. 더 열심히 공부해서 꼭 블로그에 정리해서 소개드리겠습니다.
부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해 주시면 감사하겠습니다. 🙃

 

하얀종이개발자

Reference

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) - 위키피디아 그래프(자료구조)
https://yozm.wishket.com/magazine/detail/2411/ - 그래프 알고리즘 (요즘IT)
https://dev.to/danimal92/difference-between-depth-first-search-and-breadth-first-search-6om - 깊이우선탐색과 너비우선탐색의 차이점 (dev.to)
https://www.codecademy.com/article/tree-traversal - 깊이우선탐색 vs 너비우선탐색 (codecademy)
https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/ -깊이우선탐색과 너비우선탐색의 차이점 (geeksforgeeks)
https://www.baeldung.com/cs/dfs-vs-bfs - 깊이우선탐색 vs 너비우선탐색 (Baeldung)
https://www.youtube.com/watch?v=OmYQsxreXNo&t=123s - 코딩테스트 합격자 되기 c++편 11장 그래프강의

'Algorithm & Data Structure' 카테고리의 다른 글

Union-Find로 배우는 집합(Set) 알고리즘: 개념부터 구현까지  (0) 2024.08.10
이진탐색트리(Binary Search Tree)의 핵심: 탐색, 구조, 순회 방법 쉽게 배우기  (0) 2024.08.04
해시(Hash) 함수와 충돌(Collision) 해결 전략: 효율적인 데이터 관리  (0) 2024.07.29
선형 자료구조 탐구: 스택, 큐, 덱으로 배우는 알고리즘 기초  (0) 2024.07.19
코딩 테스트 필수 개념: 시간 복잡도를 알면 문제 해결이 쉬워진다  (2) 2024.07.12

'Algorithm & Data Structure' Related Articles

티스토리툴바