DFS(깊이 우선 탐색)

깊이우선탐색의 개념

 

1) 루트 노드(또는 임의의 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

2) 직전의 갈림선이 있는 정점을 되돌아가야 하기 때문에 재귀적으로 구현하거나, 후입선출 구조의 스택을 활용

; 시작 정점의 한 방향으로 갈 수 있는 가장 깊은 경로까지 탐색하다가 끝을 만나면 직전의 갈림선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 탐색하는 방법

 

 

깊이우선탐색의 특징

 

1) 자기 자신을 호출하는 순환 알고리즘의 형태이다. 

2) 위와 같은 이유로 방문한 노드는 그 여부를 반드시 검사해야 무한 루프에 빠지지 않는다.

3) 전위 순회, 중위 순회, 후위 순회 모든 형태의 트리 순회는 모두 DFS의 한 종류이다.

4) 인접 행렬 또는 인접 리스트로 표현할 수 있다.

5) BFS보다 구현이 간단하다.

6) 단순 검색 시, BFS에 비해 느리다.

 

 

위와 같은 트리를 깊이 우선 탐색한다고 했을 때 구현 방법에 따른 노드별 탐색 순서가 다음과 같이 다르기 때문에
탐색 순서를 문제에서 지정한다면, 구현하는 방식을 달리 해야함을 유의

 

1) 재귀적으로 구현: A B E F C D G H I

2) STACK으로 구현: A D I H G C B F E

 

 

깊이 우선 탐색의 활용

 

모든 노드를 방문하고자 하는 경우이 이 방법을 선택한다.

 

 

깊이 우선 탐색의 시간 복잡도

 

DFS는 그래프(정점: N, 간선: E)의 모든 간선을 탐색한다.

1) 인접행렬로 구현 시: O(N^2)

2) 인접리스트로 구현 시: O(N+E)

 

 

백준 11724

import java.util.Scanner;

public class Main {
	static int n, m, cnt;
	static boolean[] visited;
	static boolean[][] arr;

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

		n = sc.nextInt();
		m = sc.nextInt();
		visited = new boolean[n + 1];
		arr = new boolean[n + 1][n + 1];

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			arr[a][b] = true;
			arr[b][a] = true;
		}
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				cnt++;
				visited[i] = true;
				DFS(i);
			}
		}
		System.out.println(cnt);
		sc.close();
	}

	private static void DFS(int a) {

		for (int j = 1; j <= n; j++) {
			if (!visited[j]) { // 아직 확인되지 않았고
				if (arr[a][j]) { // 둘은 연결되어 있다면...
					visited[j] = true;
					DFS(j);
				}
			}
		}
	}
}