[ 탐색 ] DFS 깊이 우선 탐색(백준 11724)

 DFS 깊이 우선 탐색

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.
시작 노드에서 출발하여 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 탐색을 수행한다.

• 재귀 함수로 구현 -> 스택 오버플로를 유의해야한다.
• 스택 자료구조 이용한다.(FILO)
• 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 등의 문제를 풀 때 사용한다.
• DFS는 한 번 방문한 노드를 다시 방문하면 안된다. 그렇기 때문에 노드 방문을 체크할 배열이 필요하다.
• 시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수
  
  

💡  DFS의 핵심 이론

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화한다.(여기서는 인접리스트)

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

 

3. 스택 자료구조에 값이 없을 때까지 반복하기

이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다.

☝🏻 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하며 진행한다.

 

 11724 : 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

출력

첫째 줄에 연결 요소의 개수를 출력한다.

입력	출력
6 5 1 2 2 5 5 1 3 4 4 6	2
6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	1

 

문제 풀이

• 노드의 개수가 크지 않기 때문에 N²을 사용해도 괜찮다.
• DFS가 몇번 돌아야 모든 노드를 탐색할 수 있는지를 구현해야한다.

 

실행 코드

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

public class P11724_DFS {
    static boolean[] visitArr; //방문여부를 저장하는 배열
    static ArrayList<Integer>[] A; //노트의 인접리스트를 저장
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 인접리스트, 방문여부 배열
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //노드의 갯수
        int M = Integer.parseInt(st.nextToken()); //간선의 갯수
        visitArr = new boolean[N+1];      //방문여부를 저장하는 배열
        A = new ArrayList[N+1];

        // N+1만큼의 ArrayList 만들기
        for(int i=1;i<N+1;i++){
            A[i] = new ArrayList<Integer>();
        }

        // 인접리스트에 데이터 채움
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken()); //줄에 첫번째 노드
            int node2 = Integer.parseInt(st.nextToken()); //줄에 두번째 노드
            A[node1].add(node2); // 방향성이 없기때문에 양방향으로 다 저장해준다.
            A[node2].add(node1);
        }

        int count = 0; // 결과값: 연결요소의 갯수

        // DFS실행
        for(int i=1;i<=N;i++){
            if(!visitArr[i]){
                count++;
                DFS(i);
            }
        }
        System.out.print(count);
    }

    private static void DFS(int v) {
        // 현재 노드가 방문한 노드일때는 통과
        if(visitArr[v])
            return;
        visitArr[v] = true;
        for(int i : A[v]){
            if(!visitArr[i])
                DFS(i);
        }

    }
}

 

 

오 개헷갈리는데