c언어 DFS알고리즘(깊이 우선 탐색)

DFS(Depth-First Search), 깊이 우선 탐색이란 전 탐색(Full-Search)의 한 종류로 더 이상 이동이 가능하지 않을 때까지 진행하다가 이동이 불가능하면 다시 전 단계로 돌아와 가능한 길을 찾아 움직이는 탐색 방법입니다. 다른 종류로는 BFS(Breadth-First search)너비 우선 탐색이 있습니다. 각종 프로그래밍 대회나 정보올림피아드에서 자구 나오는 문제 유형이므로 잘 알아두면 어려모로 도움이 되는 알고리즘입니다.

1. 1에서 2로 이동

2. 2에서 3으로 이동

3. 3에서 4로 이동

4. 4에서 더 진행할 곳이 없으므로 3으로 되돌아옴

5. 3에서 5로 이동

6. 5에서도 진행할 곳이 없으므로 3으로 되돌아옴

7. 3도 마찬가지므로 2로 되돌아옴

8. 2에서 6으로 이동

9. 2로 되돌아옴

10. 1로 되돌아옴

11. 7로 이동 (반복)

결국 그래프에서의 이동 순서는 적혀있는 순서대로 움직입니다.

이런 식으로 모든 수를 찾아 해답을 구하는 방식입니다.

문제풀이 사이트 codeup.kr 의 4024번 문제를 풀어봅시다.

http://codeup.kr/JudgeOnline/problem.php?id=4024

호수의 수를 구하는 간단한 문제입니다.

단, 

. . .

. L .

. . .

이 범위 안에 다른 호수가 있으면 하나의 호수로 간주합니다.

#include <stdio.h>
int w, h;
char lake[105][105] = { 0, };
 
void dfs(int x, int y){
    lake[x][y] = '.'; //현재 위치를 .으로 바꿈
 
    for (int i = -1; i <= 1; i++){ 
        for (int j = -1; j <= 1; j++){
            int a = x + i;
            int b = y + j; //주변 8자리를 검사
 
            if (lake[a][b] == 'L'){ //연못이 있으면
                dfs(a, b); //dfs를 다시 시작
            }
        }
    }
}
 
int main(){
    int number = 0; //연못의 개수
    scanf("%d %d\n", &w, &h);
 
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            scanf("%c ", &lake[i][j]);
        }
    }
 
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (lake[i][j] == 'L'){ //연못이 있으면
                dfs(i, j); //dfs시작
                number++;
            }
        }
    }
    printf("%d", number);
    return 0;
}
 

DFS를 실행시킬 때마다 이어져 있는 연못들은 전부 '.'로 바뀌기 때문에 DFS를 실행시킨 횟수가 연못의 개수가 되는 방법으로 풀었습니다.