[코딩테스트][알고리즘] 5. DFS (Depth First Search) 깊이 우선 탐색

DFS는 코딩테스트에서 자주 출제되는 유형이라고 하니 잘 익혀두는 것이 좋을 것 같다. 

 

DFS는 그림과 같이 탐색을 진행하는 알고리즘이다. 

 

갈때까지 가다가 더 이상 진행 할 곳이 없으면 돌아가서 다음 방법을 찾는 것이다.

 

미로를 탐색한다고 생각할때 오른벽에서 손을 떼지 않고 계속 전진하면 출구를 찾을수 있다는 아이디어가 바로

 

DFS 탐색법이라고 말 할 수 있다. 다시 말해 가장 깊은 곳까지 가는 것을 우선시 하며 탐색하는 것이다.

dfs는 stack 혹은 재귀함수로 구현 할 수 있다. 재귀함수로 구현하는게 매우 간단하기 때문에 재귀함수로 구현하는 것을 추천한다. dfs는 다음과 같이 구현 할 수 있다.

 

public static void dfs( int here ) {
		
        System.out.print(here + " ");	// 방문한 좌표를 출력
		visited[ here ] = true;		// 방문처리
		for ( int i = 0; i < N; i++ ) {		// 모든 좌표를 탐색 후
			if ( connect[ here ][ i ] && !visited[ i ]) {		// 연결되어있고, 방문하지 않았다면
				dfs( i );		// 탐색된 좌표에서 dfs 실행 
			}
		}
	}

 

추천 연습 문제 :

1. https://www.acmicpc.net/problem/2606 바이러스

해설 : https://ckdgus.tistory.com/24

2. https://www.acmicpc.net/problem/2667단지번호붙이기

해설 : https://ckdgus.tistory.com/26

 

- 추가 예정 -