깊이 우선 탐색(DFS)

Depth-first search(DFS)

• 시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문
• 최대 깊이 노드까지 방문한 다음에는 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드의 최대 깊이까지 차례때로 방문
• 스택을 사용하며 스택에 있는 노드는 아직 방문하지 않은, 방문할 예정인 노드임

1. 시작 노드를 정하고 스택에 시작 노드를 push
2. 스택이 비었는지 확인(스택이 비었으면 방문할 수 있는 모든 노드를 방문했다는 의미 -> 탐색 종료)
3. 스택에서 노드를 pop(pop한 원소는 최근에 스택에 push한 노드)
4. pop한 노드의 방문 여부를 확인. 아직 방문하지 않았다면 방문 처리
5. 방문한 노드와 인접한 모든 노드 확인. 그리고 그 중 아직 방문하지 않은 노드를 스택에 push

고려할 점

1. 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 함
2. 가장 최근에 방문한 노드를 알아야 함
3. 이미 방문한 노드인지 확인할 수 있어야 함

=> 가장 깊은 노드까지 방문한 후 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인

스택 활용

스택은 선입후출의 특성을 가지고 있기 때문에 가장 최근에 방문한 노드를 확인할 수 있음

1. 스택에 방문 예정인 노드를 push함
2. push한 노드를 pop한 후 방문한 상태인지를 확인. 만약 방문한 상태가 아니라면 방문 처리를 함.
3. 방문 처리 후 pop한 노드와 인접하면서 방문하지 않은 노드를 push
4. 2~3 과정을 반복
5. 스택이 비면 작업을 끝냄

재귀함수 활용

재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택에 쌓이고, 이때문에 깊이 우선 탐색에 활용할 수 있는 것

1. 시작 노드를 통해 dfs(시작노드)를 호출
2. dfs(시작노드)가 실행되면 시작노드를 방문 처리하고 내부적으로 dfs(인접노드)를 호출
3. 위의 과정이 반복됨
4. dfs(마지막노드) 호출 후 마지막 노드와 인접한 노드가 없으면 종료함

깊이 우선 탐색의 사용

깊이 우선 탐색은 가장 깊은 곳을 우선하여 탐색하고, 최근 방문 노드부터 다시 탐색을 진행한다는 특성이 있음

• 모든 가능한 해를 찾는 백트래킹 알고리즘 구현 시 활용
• 그래프의 사이클을 감지해야 하는 경우 활용
• 코테에서 최단 경로를 찾는 문제가 아니면 사용하는 것이 좋음

package graph;

import java.util.ArrayList;

public class dfs {
    private static ArrayList<Integer>[] adjList; // 인접 리스트를 저장할 배열
    private static boolean[] visited; // 방문 여부를 저장할 배열
    private static ArrayList<Integer> answer;

    public static void main(String[] args) {
        int V = 5; // 정점의 개수
        adjList = new ArrayList[V];
        visited = new boolean[V];
        answer = new ArrayList<>();

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

        // 간선 추가
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 2);
        addEdge(2, 0);
        addEdge(2, 3);
        addEdge(3, 3);
        addEdge(3, 4);

        // DFS 수행
        dfs(2); // 시작 노드를 2로 설정

        // 결과 출력
        System.out.println("DFS 결과 : " + answer);
    }

    private static void addEdge(int v, int w) {
        adjList[v].add(w); // v -> w 간선 추가
    }

    private static void dfs(int now) {
        visited[now] = true; // 현재 노드를 방문했음을 저장
        answer.add(now); // 현재 노드를 결과 리스트에 추가

        // 현재 노드와 인접한 노드 순회
        for (int i = 0; i < adjList[now].size(); i++) {
            int next = adjList[now].get(i);
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}