깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth-First Search)이란

그래프 순회 방법 중 하나로 시작노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서 다시 깊이 우선 탐색을 진행한다.

-전위 순회: 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 방문
-중위 순회: 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 방문
-후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 부모 순서로 방문

재귀호출로 구현

public class GraphDfsEx1 {

    static final int MAX_N = 10;
    static int N, E;   // 노드와 간선
    static int[][] Graph = new int[MAX_N][MAX_N];
    static boolean[] Visited = new boolean[MAX_N];

    static void dfs(int node) {
        // 0을 방문했다고 마킹
        Visited[node] = true;
        System.out.print(node + " ");

        // 0과 인접한 노드에 대해 탐색 시작
        // 0은 이미 방문했고, 자기 자신이므로 간선 정보가 없으므로 재귀호출 하지 않고 다음 for 수행
        // Graph[0][1] 의 의미는 0-1 간선
        for(int next = 0; next < N; next++) {
            if(!Visited[next] && Graph[node][next] != 0){
                dfs(next);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        E = sc.nextInt();

        // 간선의 갯수만큼 한 쌍씩 읽어온다.
        for(int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v= sc.nextInt();
            // 간선이 존재하므로 1로 변환
            Graph[u][v] = Graph[v][u] = 1;
        }

        // 0번 시작 노드
        dfs(0);
    }
}

스택으로 구현

public class GraphDfsEx2 {

    static final int MAX_N = 10;
    static int N, E;
    static int[][] Graph = new int[MAX_N][MAX_N];

    static void dfs(int node) {
        boolean[] visited = new boolean[MAX_N];

        Stack<Integer> myStack = new Stack<>();

        // 제일 처음에 0 노드 push
        myStack.push(node);

        while(!myStack.isEmpty()) {
            // 0 pop -> 2 pop -> 4 pop -> 3 pop -> 1 pop
            int current = myStack.pop();

            // 0은 방문한 적이 없으므로(pop 되어서) if 절 벗어나 아래 로직 수행
            // 마지막에 1이 들어오면 방문한 적이 있기 때문에 continue 되어 while문 수행
            if(visited[current]) {
                continue;
            }

            // 방문했다고 마킹
            visited[current] = true;
            System.out.print(current + " ");

            for(int next = 0; next < N; next++) {
                // 0 에서 인접한 노드들 push -> 1, 2 push -> 4 push -> 1 push (스택은 사이클이 존재하는 경우 중복으로 push 될 수 있음) -> 3 push -> 1 push
                if(!visited[next] && Graph[current][next] != 0) {
                    myStack.push(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        E = sc.nextInt();

        for(int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            Graph[u][v] = Graph[v][u] = 1;
        }

        dfs(0);
    }
}

*참고자료 - https://www.youtube.com/watch?v=0Njv04WiLV0&t=435s