[Algorithm][DFS] DFS 개념 및 구현

I. DFS(Depth First Search)란?

DFS 기본구조

깊이 우선 탐색(DFS)은 연결된 Branch를 하나 정하여 막힐 때까지 탐색하는 알고리즘이다.
미로를 탐색할 때 갈림길에서 한 방향으로 먼저 쭉 가보는 방법이라고 생각하자.

BFS와 마찬가지로 DFS도 탐색이기 때문에 모든 점을 탐색하는 방법이다.

-> 공간 복잡도 O(N)
-> 시간 복잡도 O(N+B)  (N : node, B : branch) 

주로 Flood Fill, 조합 문제 등 모든 경우의 수를 다 확인해야 하는 문제로 출제된다.
응용이 많이되므로 연습이 필요하다. BFS보단 어렵다고 개인적으로 생각함!

 

---

II. 기본원리

한 노드와 인접한 점을 모두 확인하며 확산하는 BFS와는 달리,
동일한 패턴 및 조건을 가지고 연결된 노드를 끝까지 파고 들어간다.

따라서 "재귀함수" or "While()"을 이용한다. 나는 재귀 함수가 좀 편했다!

Ex) Flood Fill로 10x10 배열을 모두 0->1로 채운다고 할 때,

1. (0,0)을 기준으로 하여 4 방향을 탐색 (탐색 순서가 동남서북이라면)
2. (0,1)로 이동해 4방향 탐색 -> (0,2) 가서 4방향 탐색... 반복
3. 맨 끝인 (0,9)에서 동쪽은 막혔으니 남쪽(1,9) 이동
4. (2,9), (3,9).... 이동 , 이하 반복

!! 주의 - 방문했던 Node는 재방문 금지.

 

---

III. 구현 코드 - Flood Fill

!! 주의 - DFS를 재귀 함수로 구현할 때는 return 하면 한 단계 전으로 간다.
           깊게 search 하면 할수록 빠져나오는데 시간도 더 오래 걸리니 이를 인지하고 구현해야 한다.

1. 모든 배열을 돌며 1의 개수를 찾는 코드 (2중 for 해도 되는데 예시로 ^^)
    10x10의 배열을 DFS로 Search

<hide/>
/*
01100
00110
00111
11111
10000
답 : 13개
*/
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;

int map[5][5] = { {0,1,1,0,0},{0,0,1,1,0},{0,0,1,1,1},{1,1,1,1,1},{1,0,0,0,0} };
int cnt{ 0 };


/*
탈출조건으로 return 해도 좋고,
for문의 nexty, nextx를 탐색해서 continue;해도 괜찮다.
하지만 탈출조건 하면 1단계 더 깊이 들어가는 것 생각하자!
*/
void DFS(int y, int x) {

	if (y == -1 or x == -1 or
		y == 5 or x == 5) return; // 이것보단 for문 안에 continue가 좋음.

	map[y][x] = 0; //방문처리
	cnt++;

	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { 1,-1,0,0 }; // 4방향 search

	for (int d = 0; d < 4; d++) {
		int nexty = y + dy[d];
		int nextx = x + dx[d];
		if (map[nexty][nextx]) DFS(nexty, nextx); // 다음이 1이면 확산
	}

	return;
}

int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (map[i][j]) DFS(i, j); // 1일 때만 DFS시작하여 확산
		}
	}
	cout << cnt << endl; // 13
	return 0;
}

 

2. 0과 1로 이루어진 배열에서 1의 그룹이 몇 개인지 찾는 코드
 7x7 배열에서 1을 확인하면 그 위치부터 DFS시작

다음과 같은 그룹

<hide/>

#include <stdio.h>
#include <iostream>
using namespace std;

int map[7][7] = { {0,1,1,0,1,0,0},{0,1,1,0,1,0,1},{1,1,1,0,1,0,1},{0,0,0,0,1,1,1},
				  {0,1,0,0,0,0,0},{0,1,1,1,1,1,0},{0,1,1,1,0,0,0} };
                  
int groupcnt{ 0 }; // 1이 있는 그룹의 개수
int maxsum{ 0 }; // 그룹 내 1의 개수 중 max 값
int innersum{ 0 }; // 그룹 내 1의 개수

void DFS(int y, int x) {

	map[y][x] = 0; //방문처리
	innersum++;

	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { 1,-1,0,0 }; // 4방향 search

	for (int d = 0; d < 4; d++) {
		int nexty = y + dy[d];
		int nextx = x + dx[d];

		if (nexty == -1 or nextx == -1 or
			nexty == 7 or nextx == 7) continue; // 밖으로 나가면 무시

		if (map[nexty][nextx]) DFS(nexty, nextx); // 다음이 1이면 확산
	}

	return;
}

int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (map[i][j]) {
				innersum = 0;
				DFS(i, j); // 1일 때만 DFS시작하여 확산
				groupcnt++; // 그룹 1개 추가
				if (maxsum < innersum) maxsum = innersum; //그룹 내 1의 수 최대값 업데이트
			}
		}
	}
	printf("그룹 수:%d, 최대 그룹:%d\n", groupcnt, maxsum); //3,9
	return 0;
}

 

3. 가능한 합의 숫자 (조합)
5개의 수를 임의로 조합하여 N이라는 수를 만들 수 있을까?

<hide/>
#include <stdio.h>
#include <iostream>
using namespace std;

int numarr[5] = { 1,7,9,17,26 };
int target[3] = { 18,33,49 }; // Y,Y,N
bool istrue{ 0 }; // DFS도중에 찾았는가?

// 전역변수로 flag 두고 True / False 표시해도 된다.
void DFS(int idx, int sum, int targetnum) {

    // DFS이므로 모든 경우를 탐색하게 된다.
    // 따라서 istrue도 조건문에 넣어주어 가지치기해서 시간 절약
	if (sum == targetnum or istrue==1) {
		istrue = 1;
		return;
	}

	if (idx == 5) return; // 인덱스 넘어가면 반환

	DFS(idx + 1, sum + numarr[idx], targetnum); // 해당 idx의 숫자를 포함하여 더함
	DFS(idx + 1, sum, targetnum); // 해당 idx의 숫자를 포함하지 않음

	return;
}

int main() {
	for (int i = 0; i < 3; i++) {
		istrue = 0;
        
		DFS(0, 0, target[i]);
        
		if (istrue) cout << "True" << endl;
		else cout << "False" << endl;
	}
	return 0;
}

 4. 기타 응용

다양한 부분으로 응용이 많이 되어서... DFS문제다! 하고 한방에 알 수 있는 것은 Flood Fill정도이다.
다만, DFS는 한 단계씩 진행하며 모든 경우를 확인해야 하므로
다양한 경우 모두 파악해야 할 때, DFS방법으로 접근해보자.

중요한 것은 가지치기로 실행 시간을 많이 줄이도록 해야한다.

나는 DFS 응용문제가 정말 어려웠다. 문제를 많이 풀자ㅠㅠ
농장탈출/ 건물세우기/ 책꽂이/ 월드컵/ 스도쿠/ 벽장문의이동/ 매직스타/ 페그솔리테어 등등