[코테 알고리즘] DFS(Depth First Search)

그래프의 모든 노드를 탐색하는 DFS(Depth First Search)

---

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

시작노드에서 출발하여
리프노드까지 내려가고 부모에게 올라가,
다시 리프노드까지 내려가는 것을 반복하는 과정을 ' 깊이우선탐색(DFS) '라고 한다.

🕑 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수)
[모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니]

DFS와 재귀함수

---

DFS는 재귀함수로 구현하며,
재귀함수란 '자기 자신'을 Function call(함수 호출)하여 동작하는 방식을 말한다.
(종료조건과 재귀적확장이 있어야 한다.)

DFS 코드 구현, 백준 1260 DFS

---

  🪅 에지리스트를 인접리스트로 구현할 수 있는가
  🪅 방문배열을 만들어야 하는 이유를 아는가
  🪅 List<Integer[]> listd와 List<Integer>[] list의 차이를 아는가

⚠️ 한번 방문한 노드를 다시 방문하면 안되므로, 방문여부를 체크할 배열(방문배열)이 필요하다.


** (보통 입력은 에지리스트로 주어지고, 이를 인접리스트로 바꿔 DFS구현한다) **

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 백준 1260번 DFS
 * 
 * 입력:
 * 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 
 * 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 
 * 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
 *
 * 출력:
 * 첫째 줄에 DFS를 수행한 결과를
 * V부터 방문된 점을 순서대로 출력하면 된다.
 * 
 */
public class B1260_DFS_이우엽 {
    static List<Integer>[] tree;
    static boolean[] isVisited;
    public static void DFS(int node) {
        isVisited[node] = true;
        System.out.print(node + " ");
        // 인접 정점 방문, 재귀적 확장
        for(int adj : tree[node]) {
            // 종료조건, 이미 방문했으면 continue
            if(isVisited[adj]) continue;
            isVisited[adj] = true;
            DFS(adj);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        // 정점의 개수 N
        int N = Integer.parseInt(token.nextToken());
        // 간선의 개수 M
        int M = Integer.parseInt(token.nextToken());
        // 시작정점 번호 V
        int V = Integer.parseInt(token.nextToken());

        // 인덱스0은 쓰지 않고 1부터 N까지 인덱스 사용
        tree = new ArrayList[N+1];
        isVisited = new boolean[N+1];

        // 배열의 각 요소를 ArrayList로 초기화
        for(int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        // 간선의 개수만큼 입력받는다
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(token.nextToken());
            int v = Integer.parseInt(token.nextToken());
            tree[u].add(v);
        }

        // test 출력
//        for(int i = 0; i < tree.length; i++) {
//            System.out.println(i +": " + tree[i]);
//        }
        DFS(1);
    }
}