DFS 기본 학습

728x90

백준에서 알고리즘을 풀다가 그래프 탐색에 대해서 문제를 직면 하였다. 감이 하나도 안잡히는 알고리즘으로 이번 기회에 학습하게 되어 정리해보고자 한다.

그래프 탐색은 DFS, BFS 두 알고리즘으로 해결할 수 있다고 한다. 내가 먼저 학습한 것은 깊이 우선 탐색인 DFS이다.

DFS란?

Depth First Search ( 깊이 우선 탐색 )의 약자로, 그래프 탐색에서 한 정점에서 출발하여 더 깊은 곳까지 탐색한 후 다른 경로를 탐색한다.

DFS 동작 방식

1. 시작 정점에서 출발한다.

2. 연결된 다른 정점으로 이동한다.

3. 더 이상 갈 곳이 없으면 이전 정점으로 되돌아온다.

4. 이 과정을 반복하여 모든 연결된 정점을 방문한다.

DeepDive

기본적인 개념은 확인했으니 이제 적용해보자.

우선 각 정점을 연결하는 정보를 저장할 배열이 필요하다.

static ArrayList<Integer>[] graph;

처음에 코드를 보고 의아했다. 이게 무슨의미인지 잘 이해가 안가는 생소한 자료구조였다.

이에 어떻게 내부 구조가 되는지 하나씩 넣어보면서 이해했다.

[	
{},     // 0번 노드은 생략한다.
{},		// 1번 노드
{},		// 2번 노드
{},		// 3번 노드
{},		// 4번 노드
{}		// 5번 노드
]

위와 같이 배열에는 하나의 ArrayList<Integer> 라는 객체가 저장되는 구조이다.

각 노드별로 연결된 간선을 입력받아서 노드별로 저장한다.

예를 들어

1 번은 2번 노드와 연결
1 번은 3번 노드와 연결
2번은 4번 노드와 연결
2번은 5번 노드와 연결

[
{2, 3},
{4, 5},
{},
{},
{},
]

이렇게 각 노드별로 연결된 노드를 저장하고 있다.

이제 위 노드들을 탐색하면서 노드를 이동하면서 검사한다.

먼저, 한 번 탐색했던 노드는 다시 탐색하지 않도록 flag 배열이 필요하다.

class Dfs{
  static ArrayList<Integer>[] graph;
  static boolean[] visited;
}

그래프 탐색

각 그래프를 탐색하기 위한 재귀 코드를 작성한다.

class Dfs {
  static ArrayList<Integer>[] graph;
  static boolean[] isVisited;
  
  public staic void dfs(int node) {
    isVisited[node] = true;
    System.out.printf("now Visited node is : %d\n", node);
    
    for (int next : graph[node]) {
      if (!isVisited[next]) {
        dfs(next);
      }
    }
  }

Appled Problem

연결되어 있는 노드의 개수를 구하는 문제가 출제된다. 이를 위해서 하나의 변수에 count 횟수를 저장하면 된다.

class Viruns {
  private static ArrayList<Integer>[] graph;
  private static boolean[] visited;
  private static int count;
  
  private static void dfs(int node) {

    visited[node] = true;
   
    for (int next : graph[node]) {

      if (!visited[next]) {
        count++;
        dfs(next);
      }
    }
  }
}

Finish

한 번 경험한 것으로 모든 문제를 해결할 수는 없다.

학습한 기본적인 개념을 체득하여 다양한 문제를 해결하기 위해서 경험해보고 고민해보는 시간이 필요하다.