DFS

---

DFS란?

Depth-First-Search의 약어로, 깊이 우선 탐색이라는 그래프 탐색 방법중 하나이다.

알고리즘 문제 풀이는 수학문제를 푸는 것과 같이 문제 타입을 확인하고 학습한 절차에 따라 문제를 풀면된다. 일단 DFS를 확용한 그래프 전체 탐색 문제라고 생각되면 아래와 같은 절차로 문제를 푼다.

1. 리턴값을 정한다. (전역변수로 선언)

class Solution {
    int retNumber;
    ...
}

2. 환경 데이터 등의 변하지 않는 정보는 전역변수로 선언한다.

class Solution {
	...
    Character[] alphabet = {'A', 'E', 'I', 'O', 'U'};
    ...
}

3. 문제에서 주어진 정보와 방문여부를 매개변수로 하는 DFS 함수를 구현한다.

public void dfs(int k, int[][] dungeons, boolean[] visited) {}

tip

노드의 중복 방문을 막을 필요가 있을때, 방문여부를 체크할 배열을 별도로 만드는것이 좋다.

4. dfs 함수의 탈출 조건을 정한다.

• 재귀 호출을 통한 탐색이기때문에 탈출 조건을 설정하여 무한루프를 벗어난다.

private void dfs(String currentWord, int number) {
	...
	//탈출조건
	if (currentWord.length() >= 5)
            return;
	...
}

5. 리턴값 갱신 조건을 정한다

private void dfs(String currentWord, int number) {
	...
	if (currentWord.equals(targetWord)){
		retNumber = number;
		return;
	}
	...

6. 각 노드 배열을 순회하며 방문할 경우 dfs 함수를 재귀적으로 호출

private void dfs(String currentWord, int number) {
	...
	for (int index= 0; index < alpha.length; index++){
		dfs(currentWord + alpha[index], tempNumber + 1);
	}
}

재귀 함수 호출 후에는 매개변수를 노드 방문 전으로 돌리고, for문을 진행한다.

---

연결문서