DFS | 자바

(이코테 2021 강의 몰아보기) 3. DFS & BFS)를 보면서 작성한 글입니다.

DFS란

DFS는 대표적인 그래프 탐색 알고리즘 중 하나입니다. 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 말합니다. DFS라는 말에서도 알 수 있듯이 깊이(Depth)를 우선적으로 탐색합니다.

깊이를 우선적으로 탐색한다는 말은 아래 그림과 같습니다.

번호가 낮은 인접 노드부터 DFS로 위 그래프를 탐색하면 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5 순으로 탐색하게 됩니다.

DFS 구현

DFS는 스택 혹은 재귀함수로 구현할 수 있습니다. 하지만, 보통 편리성 때문에 스택보다 재귀함수를 이용해 구현하는 경우가 많습니다.

import java.util.*;
 
public class Main {
  public static boolean[] visited = new boolean[9];
  public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
 
  public static void dfs(int x) {
    visited[x] = true;
    System.out.print(x + " ");
 
    for (int i = 0; i < graph.get(x).size(); i++) {
        int y = graph.get(x).get(i);
        if(!visited[y]) dfs(y);
    }
  }
 
  public static void main(String[] args) {
    // 그래프 초기화
    for (int i = 0; i < 9; i++) {
      graph.add(new ArrayList<Integer>());
    }
 
    // 노드 1에 연결된 노드 정보 저장 
    graph.get(1).add(2);
    graph.get(1).add(3);
    graph.get(1).add(8);
 
    // 노드 2에 연결된 노드 정보 저장 
    graph.get(2).add(1);
    graph.get(2).add(7);
 
    // 노드 3에 연결된 노드 정보 저장 
    graph.get(3).add(1);
    graph.get(3).add(4);
    graph.get(3).add(5);
 
    // 노드 4에 연결된 노드 정보 저장 
    graph.get(4).add(3);
    graph.get(4).add(5);
 
    // 노드 5에 연결된 노드 정보 저장 
    graph.get(5).add(3);
    graph.get(5).add(4);
 
    // 노드 6에 연결된 노드 정보 저장 
    graph.get(6).add(7);
 
    // 노드 7에 연결된 노드 정보 저장 
    graph.get(7).add(2);
    graph.get(7).add(6);
    graph.get(7).add(8);
 
    // 노드 8에 연결된 노드 정보 저장 
    graph.get(8).add(1);
    graph.get(8).add(7);
 
    dfs(1);
  }
}

1. 2차원 배열을 이용해서 그래프를 표현합니다. graph의 i번째에 있는 배열은 i와 연결된 노드들입니다.
2. 탐색했는지 여부를 체크하는 visited 배열을 생성합니다.
3. dfs 함수의 매개변수 x는 탐색을 시작하고자 하는 노드를 가리킵니다. dfs 함수는 해당 노드를 탐색했다면 방문처리(true)를 해주고 연결된 다른 노드를 재귀적으로 방문합니다.

DFS 관련 문제

• 내가 푼 문제
• 실버 추천 문제