[Algorithm] DFS(Depth First Search)

오늘 알아볼 알고리즘은 DFS이다.

오늘 백신을 맞아서 백신공가로 쉬고있는데, 사실 좀 피곤한거같다. 이거만 후딱 쓰고 좀 쉬어야겠다.

 

DFS란?

깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

그래프 탐색 알고리즘 중 하나로, 코딩테스트에도 많이 나오고 프로그래머라면 알고 있어야 하는 알고리즘 중에 하나이다.

출처 - 위키백과

위와 같은 방식으로 너비가 아니라 깊이를 우선으로 탐색하는 방식이다.

 

이와 관련된 간단한 문제를 꼽으면 백준 11123번 양 한마리.. 양 두마리... 가 있다.

https://www.acmicpc.net/problem/11123

11123번: 양 한마리... 양 두마리...

나는 이렇게 풀었다.

#include <iostream>
#include <vector>
using namespace std;

void DFS(int x, int y, int arr[100][100], bool ck[100][100], int width, int height);

int main()
{
int testCase = 0;
int width = 0, height = 0;
int arr[100][100];
bool check[100][100];
vector<int> answer;
int cnt;
cin >> testCase;

for (int k = 0; k < testCase; k++)
{
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
arr[i][j] = 0;
check[i][j] = false;
}
}
cnt = 0;

cin >> width >> height;

for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
char temp;
cin >> temp;
if (temp == '#')
{
arr[i][j] = 1;
}
else
{
arr[i][j] = 0;
}
}
}
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (arr[i][j] == 1)
{
DFS(i, j, arr, check, width, height);
cnt++;
}
else
{
continue;
}
}
}
answer.push_back(cnt);
}

for (auto p : answer)
{
cout << p << endl;
}

}

// 만약 이어져 있을 경우 하나로 보면 됨.

void DFS(int x,int y,int arr[100][100], bool ck[100][100], int width, int height)
{
int dirX[4] = { -1,0,1,0 };
int dirY[4] = { 0,1,0,-1 };

ck[x][y] = true;
arr[x][y] = 0;

for (int i = 0; i < 4; i++)
{
int nextX = x + dirX[i];
int nextY = y + dirY[i];

if (nextX < 0 || nextY < 0 || nextX >= width || nextY >= height) {continue;}
if (ck[nextX][nextY]) { continue; }
if (arr[nextX][nextY] == 0) { ck[nextX][nextY] = true; continue; }
// 3개의 경우를 모두 걸렀으면, 이제부터 시작

DFS(nextX, nextY, arr, ck, width, height);
}

}

 

1. 현재 탐색중인 인덱스가 #일 경우, #의 상하좌우를 탐색한다.

2. 상하좌우도 #일 경우, 똑같이 탐색한다.

3. #이 아닐 경우, 탐색을 종료한다.

4. 탐색을 종료했을 때는 check를 true로 바꿔주고, 현재 arr를 0으로 만들어준다.

5. 그러면 이제 다음번에 이미 check된 경우 arr를 탐색하지 않는다. 

6. 한 영역을 모두 체크했다고 했을 때 카운트의 갯수를 1 늘린다.

 

1~6의 과정을 모두 했을 때의 결과를 vector에 push한 후에 마지막에 출력해주었다.

결과적으로 성공했다!