[알고리즘] DFS / BFS

그래프란

그래프는 노드와 간선으로 표현된다.

• 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.
  

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

  int[][] graph = new int[vertices][vertices];

  인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.

  이 때 연결이 되어 있지 않는 노드끼리는 무한의 비용이라고 작성한다.

  

  • [[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]
    • 1차, 2차 모두 숫자(인덱스)가 작은 수부터 나열
    • 0번 노드는 1과 2번 노드 모두 연결
    • 본인 스스로에 대한 값 또한 저장을 한다.
      • [0, 7, 5] ← 0번 노드는 0번 노드에 대한 가중치가 0임, 0번 노드는 1번 노드에 대한 가중치가 7임, 0번 노드는 2번 노드에 대한 가중치가 5임.

• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

  List<List<Integer>> graph = new ArrayList<>();

  모든 노드에 연결 된 노드에 대한 정보를 차례대로 연결하여 저장한다.

  

  • [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
    • 1차, 2차 모두 숫자(인덱스)가 작은 수부터 나열
    • 본인에 대한 가중치는 계산하지 않고, 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

인접 리스트 방식은 정보를 얻는 속도가 느리다.

• 예를 들어 노드 1과 노드 7이 연결 되어 있는 상황을 살펴볼 때 인접 행렬 방식에서는 graph[1][7]만 확인하면 된다.
  [[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]

그러나 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인 해야 한다.
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

정리하자면 다음과 같다.

인접 행렬은 모든 노드 간 연결 정보를 표 형태로 미리 전부 써 둔 것

• “1번 줄 7번째 칸을 보면 바로 확인 가능”
  

인접 리스트는 1번 노드에 대한 연결된 노드 목록만 갖고 있음

• “1번 노드의 친구 목록을 보고, 7번이 포함됐는지 직접 찾는 방식”
  

DFS

깊이 우선 탐색이라고 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

이 알고리즘은 특정한 경로로 탐색 하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

DFS는 스택 자료구조를 이용해 아래의 과정을 거치며 동작한다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다.
   1. 이 때 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

→ 이 때 실제로는 스택을 사용하지 않아도 된다.

public static void dfs(int i) {
    visit[i] = true;
    System.out.print(i + " ");
    
    for (int j = 0; j < n; j++) {
        if (map[i][j] != 0 && map[i][j] != INF && !visit[j]) { // 연결되어 있고 아직 방문하지 않았을 경우
            dfs(j);
        }
    }
}

• 주어진 인접 행렬 : [[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]

  아래는 대략적인 흐름이다.

  

  1. 0번 노드부터 시작한다.
  2. 0번 노드에서 연결된 노드들인 1 노드를 방문한다.
  3. 1번 노드에서 0번 노드는 이미 방문 처리 되어있고, 2번 노드는 연결이 안되어 있으니 2번 노드로 진행 된다.

BFS

너비 우선 탐색이라고 하며, 가까운 노드부터 탐색하는 알고리즘이다.

이 알고리즘은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

BFS는 큐 자료구조를 이용해 아래의 과정을 거치며 동작한다.

1. 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

public static void bfs(int i) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(i);
    visit[i] = true;

    while (!q.isEmpty()) {
        int temp = q.poll();
        System.out.print(temp + " ");

        for (int j = 0; j < n; j++) {
            // 가중치가 0보다 크면 연결된 것으로 간주 (자기 자신 제외)
            if (map[temp][j] > 0 && !visit[j]) {
                q.offer(j);
                visit[j] = true;
            }
        }
    }
}

• 주어진 인접 행렬 : [[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]

  아래는 대략적인 흐름이다.

  

  1. 0번 노드부터 시작한다.

  2. 큐에 0번 노드가 삽입 되고, 방문 처리 한다.

  3. 큐에서 0번 노드를 빼고, 0번 노드와 연결 된 1번, 2번 노드를 각각 큐에 넣고 방문 처리 한다.

     → 인접한 노드가 여러 개 있을 때 숫자가 작은 노드부터 먼저 큐에 삽입한다.

DFS는 더 깊게 가기 위해 재귀를 사용하고, BFS는 더 넓게 가기 위해 큐 자료구조를 사용한다.

DFS와 BFS 문제를 풀 때 1차원이나, 2차원 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있게

어느 문제에서 어느 알고리즘을 사용 해야 하는가?

간단하게 분류 하자면 다음과 같다.

DFS 알고리즘은 경로의 존재 여부·완전 탐색·백트래킹이 필요할 때 사용된다.

그 이유로는 한 노드에서 시작해 가능한 경로를 끝까지 “끝까지 들여다본 뒤” 돌아와서 다른 분기로 넘어가기 때문에, 구조적으로 백트래킹이나 재귀 처리에 유리하다.

예시는 아래와 같다.

• 단순히 “어떤 길이든 목표 정점에 도달할 수 있는가?”만 물을 때
• 그래프의 모든 연결 요소(connectivity)나 사이클 존재 여부를 확인할 때
• 깊이 우선으로 내려가면서 백트래킹을 해야 하는 순열·조합·부분집합 생성, 스도쿠·N-Queen 같은 완전 탐색 문제
• 위상 정렬, 강한 연결 요소 분해처럼 재귀 호출로 구조를 쪼개 처리할 때

BFS 알고리즘은 최단 거리(또는 최소 단계)를 구해야 할 때 사용 된다.

그 이유로는 모든 인접 정점을 우선 순위 없이 한 단계(거리)씩 확장해 나가므로, 도달 시점에 그 경로가 곧 최단거리임이 보장되기 때문이다.

예를 들어 예시들은 아래와 같다.

• 무가중치 그래프에서 두 노드 간의 최단 경로(단계 수)를 구해야 할 때
• 퍼즐(8퍼즐, 슬라이딩 퍼즐)처럼 “n번의 이동으로 목표 상태에 도달할 수 있는가?”를 묻는 문제
• 미로에서 출발점부터 목표 지점까지 최소 칸수를 구하는 문제
• “몇 단계 이내에 도달 가능한 정점이 몇 개인가?” 같은 레벨별 탐색이 필요할 때