221018 DFS, 깊이 우선 탐색 (Depth Fisrt Search)

Jongleee·2022년 10월 19일
TIL
1

TIL

목록 보기
81/737

DFS, 깊이 우선 탐색 (Depth Fisrt Search)

"더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘이다.

미로 찾기처럼 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면

뒤로 돌아와 다른 경로로 뻗어있는 정점을 타고 방문을 재개하는 방식으로 동작한다.

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

  • 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. (완전 탐색 알고리즘에 자주 이용됨)

DFS의 특징

  • 자기 자신을 호출하는 순환 알고리즘의 형태
  • 트리 순회(전위, 중위, 후위 순회)는 모두 DFS의 한 종류
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지의 여부를 반드시 검사해야함(안하면 무한루프 빠질 위험 있음)

DFS의 수행 과정

  1. a 노드(시작 노드)를 방문한다.
    • 방문한 노드는 방문했다고 표시한다.
  2. a와 인접한 노드들을 차례로 순회한다.
    • a와 인접한 노드가 없다면 종료한다.
  3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
    • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다. (단계 1 다시)
  4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
    • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
    • 아직 방문이 안 된 정점이 없으면 종료한다.
    • 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

구현 방법 2가지

  1. 순환 호출 이용(재귀)
  2. 명시적인 스택 사용 - 인접한 정점들을 스택에 저장하였다가 다시 꺼내어 작업

그래프 표현하기

정점의 개수, 간선의 개수, 탐색을 시작할 정점을 번호를 입력받는다.

노드 방문 여부를 검사하기 위한 boolean 배열도 선언한다.

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 정점의 개수 
int m = sc.nextInt(); // 간선의 개수 
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
  1. DFS 인접 리스트로 구현
    LinkedList에 정점과 간선을 넣어 인접 리스트를 만든다.
LinkedList<Integer>[] adjList = new LinkedList[n + 1];

for (int i = 0; i <= n; i++) {
	adjList[i] = new LinkedList<Integer>();
}

// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
	int v1 = sc.nextInt();
	int v2 = sc.nextInt();
	adjList[v1].add(v2);
	adjList[v2].add(v1);
}

for (int i = 1; i <= n; i++) { // 방문 순서를 위해 오름차순 정렬 
	Collections.sort(adjList[i]);
}

System.out.println("DFS - 인접리스트");
dfs_list(v, adjList, c);

1-1. 재귀를 이용해 DFS 구현
처음 DFS 함수를 호출하게 되면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점부터 DFS 탐색을 시작한다.

정점을 방문하면 visited[v]에 true 값을 넣어 방문했다고 표시한 뒤 정점을 출력한다.

현재 정점과 인접한 정점들을 찾기위해 인접 리스트에 Iterator를 이용해 접근해 인접 정점을 탐색한다.

정점 v의 인접리스트를 순회하며 아직 방문하지 않은 visited가 false인 정점을 찾는다.

인접한 정점 w를 찾는다면 w에서부터 다시 DFS를 한다.

더 이상 방문하지 않은 정점이 없을 때까지 탐색을 하며 DFS를 하는 것이다.

// DFS - 인접리스트 - 재귀로 구현 
public static void dfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
	visited[v] = true; // 정점 방문 표시
	System.out.print(v + " "); // 정점 출력

	Iterator<Integer> iter = adjList[v].listIterator(); // 정점 인접리스트 순회
	while (iter.hasNext()) {
		int w = iter.next();
		if (!visited[w]) // 방문하지 않은 정점이라면 
			dfs_list(w, adjList, visited); // 다시 DFS
	}
}
  1. DFS 인접 행렬로 구현
    2차원 배열에 정점과 간선을 넣어 인접 행렬을 만든다.
int[][] adjArray = new int[n+1][n+1];

// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for(int i = 0; i < m; i++) {
	int v1 = sc.nextInt();
	int v2 = sc.nextInt();

	adjArray[v1][v2] = 1;
	adjArray[v2][v1] = 1;
}

System.out.println("DFS - 인접행렬 / 재귀로 구현");
dfs_array_recursion(v, adjArray, visited);
Arrays.fill(visited, false); // 스택 DFS를 위해 visited 배열 초기화

System.out.println("\n\nDFS - 인접행렬 / 스택으로 구현");
dfs_array_stack(v, adjArray, visited, true);

2-1. 재귀를 이용해 DFS 구현
인접리스트에서 재귀를 이용해 구현했던 방법과 동일하다.

//DFS - 인접행렬 / 재귀로 구현 
public static void dfs_array_recursion(int v, int[][] adjArray, boolean[] visited) {
	int l = adjArray.length-1;
	visited[v] = true;
	System.out.print(v + " ");

	for(int i = 1; i <= l; i++) {
		if(adjArray[v][i] == 1 && !visited[i]) {
			dfs_array_recursion(i, adjArray, visited);
		}
	}
}

2-2. 스택을 이용해 DFS 구현
처음 DFS 함수를 호출하게 되면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점 부터 DFS 탐색을 시작한다.

스택을 생성하고 시작 정점 v의 값을 스택에 넣는다.

  1. 스택의 top에 있는 정점을 기준으로 간선이 연결되어 있고(인접하고), 아직 방문되지 않은 정점을 찾는다.
  2. 조건에 맞는 정점을 찾는다면 해당 정점을 방문했음으로 표시 후, 스택에 넣고 break를 건다.
    • break를 걸어줌으로써, 찾은 정점을 기준으로 다시 탐색이 진행된다.
    • 이를 반복함으로써 DFS를 수행하는 것이다.
  3. 연결된 간선이 없고, 방문하지 않은 정점을 찾지 못한다면, 더이상 탐색할 수 없기에 pop()을 해 다시 돌아간다.
//DFS - 인접행렬 / 스택으로 구현 
public static void dfs_array_stack(int v, int[][] adjArray, boolean[] visited, boolean flag) {
	int l = adjArray.length-1;
	Stack<Integer> stack = new Stack<Integer>();
	stack.push(v);
	visited[v] = true;
	System.out.print(v + " ");

	while(!stack.isEmpty()) {
		int w = stack.peek();
		flag = false; 

		for(int i = 1; i <= l; i++) {
			if(adjArray[w][i] == 1 && !visited[i]) {
				stack.push(i);
				System.out.print(i + " ");
				visited[i] = true;
				flag = true;

				break;
			}
		}

		if(!flag) {
			stack.pop();
		}
	}
}

전체 코드
1. 인접 리스트로 구현한 DFS

import java.util.*;

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

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

		boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

		LinkedList<Integer>[] adjList = new LinkedList[n + 1];

		for (int i = 0; i <= n; i++) {
			adjList[i] = new LinkedList<Integer>();
		}

		// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
		// 입력으로 주어지는 간선은 양방향이다.
		for (int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			adjList[v1].add(v2);
			adjList[v2].add(v1);
		}

		for (int i = 1; i <= n; i++) { // 방문 순서를 위해 오름차순 정렬 
			Collections.sort(adjList[i]);
		}

		System.out.println("DFS - 인접리스트");
		dfs_list(v, adjList, visited);
	}
	
	// DFS - 인접리스트 - 재귀로 구현 
	public static void dfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
		visited[v] = true; // 정점 방문 표시
		System.out.print(v + " "); // 정점 출력

		Iterator<Integer> iter = adjList[v].listIterator(); // 정점 인접리스트 순회
		while (iter.hasNext()) {
			int w = iter.next();
			if (!visited[w]) // 방문하지 않은 정점이라면 
				dfs_list(w, adjList, visited); // 다시 DFS
		}
	}

}

입력

5 5 3
5 4
5 2
1 2
3 4
3 1

출력

DFS - 인접리스트
3 1 2 5 4
  1. 인접 행렬로 구현한 DFS
import java.util.*;

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

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

		boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

		int[][] adjArray = new int[n+1][n+1];

		// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
		// 입력으로 주어지는 간선은 양방향이다.
		for(int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();

			adjArray[v1][v2] = 1;
			adjArray[v2][v1] = 1;
		}

		System.out.println("DFS - 인접행렬 / 재귀로 구현");
		dfs_array_recursion(v, adjArray, visited);
		Arrays.fill(visited, false); // 스택 DFS를 위해 visited 배열 초기화

		System.out.println("\n\nDFS - 인접행렬 / 스택으로 구현");
		dfs_array_stack(v, adjArray, visited, true);
	}
	
	//DFS - 인접행렬 / 재귀로 구현 
	public static void dfs_array_recursion(int v, int[][] adjArray, boolean[] visited) {
		int l = adjArray.length-1;
		visited[v] = true;
		System.out.print(v + " ");

		for(int i = 1; i <= l; i++) {
			if(adjArray[v][i] == 1 && !visited[i]) {
				dfs_array_recursion(i, adjArray, visited);
			}
		}
	}

	//DFS - 인접행렬 / 스택으로 구현 
	public static void dfs_array_stack(int v, int[][] adjArray, boolean[] visited, boolean flag) {
		int l = adjArray.length-1;
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(v);
		visited[v] = true;
		System.out.print(v + " ");

		while(!stack.isEmpty()) {
			int w = stack.peek();
			flag = false; 

			for(int i = 1; i <= l; i++) {
				if(adjArray[w][i] == 1 && !visited[i]) {
					stack.push(i);
					System.out.print(i + " ");
					visited[i] = true;
					flag = true;
					
					break;
				}
			}

			if(!flag) {
				stack.pop();
			}
		}
	}
	
}

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

DFS - 인접행렬 / 스택으로 구현
1 2 4 3

DFS 시간복잡도

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우

  • 그래프가 인접 리스트로 표현된 경우 O(n+e)
  • 인접 행렬로 표현된 경우 O(n^2)이다.
    희소 그래프인 경우 인접 리스트의 사용이 인접 행렬보다 유리

(희소 그래프는 그래프 내에 적은 수의 간선을 가지는 그래프로 인접 행렬을 사용하면 메모리의 낭비가 크기 때문)

출처:https://minhamina.tistory.com/m/22

profile
Jongleee
이전 포스트

221017 BFS, 너비 우선 탐색(Breadth First Search)

다음 포스트

221019 String, StringBuffer, StringBuilder 차이 및 장단점

0개의 댓글