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

개념

- 특정 노드를 기준으로 가장 깊은 노드를 우선적으로 탐색하는 알고리즘.

- 탐색중인 정점의 연결된 노드에 방문한 적이 없다면 해당 노드를 스택에 삽입하고 방문 이력을 저장한다.

- 탐색중인 정점에 연결된 노드가 없거나 이미 방문한 적이 있다면 스택의 최상단을 제거한다.

- 즉, 스택에 노드를 넣고 그와 연결된 모든 노드를 방문하여 스택에 삽입하고 삭제하는 과정을 반복한다.

탐색 그래프

그래프 표현 - 인접행렬

	static boolean[] check;
	static int[][] map;
	
	static void dfs(int x) {
		
		//해당 노드 방문한경우 스택에서 제거
		if(check[x]) return;
		
		//방문하지 않았다면 방문 처리
		check[x] = true;
		System.out.println(x);
		
		//해당 노드의 인접 노드 확인
		for (int i = 0; i < map[x].length; i++) {
			int c = map[x][i];
			
			//간선이 있으면서 방문하지 않았다면 
			if(c == 1 && !check[i]) {
				dfs(i);
			}
		}
		
	}
	public static void main(String[] args) {
		int[][] edgeArr = {
						{1,2}
						,{1,3}
						,{2,3}
						,{2,4}
						,{3,5}
					  };
		
		map = new int[6][6];
		check = new boolean[6];
		
		//간선 설정
		for (int i = 0; i < edgeArr.length; i++) {
			int temp1 = edgeArr[i][0];
			int temp2 = edgeArr[i][1];
			map[temp1][temp2] = map[temp2][temp1] = 1; 
		}
		
		dfs(1);
	}

 

※ 장점

- 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. (그래프의 높이 만큼의 공간만을 요구)

- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

※ 단점

- 해가 없는 경로에 깊이 빠질 가능성이 있다. (무한루프)

따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미.