[알고리즘] DFS(Depth First Search) 깊이 우선 탐색

코딩테스트에서 자주 쓰이는 알고리즘 중 하나입니다.

트리 구조에서 목표 노드까지 깊이 우선 탐색해 빠르게 목표 노드까지 갈 수 있는 알고리즘 중 하나죠

이와 비슷한 알고리즘 중 하나인 BFS란 알고리즘도 있는데 그 알고리즘은 너비 우선 알고리즘 으로써

큐 자료구조를 사용하고 DFS는 스택 자료구조를 사용합니다.

DFS는 일반적으로 재귀 함수를 이용합니다.

 

 

1. 스택이란?

---

스택(Stack)은 쉽게 프링글스 과자 통을 생각해 봅시다.

과자통이 있고 맨 위쪽부터 맨 아래쪽까지 과자가 들어 있죠

이 상황속 저희가 과자를 어떻게 먹죠?

위에서 부터 먹습니다.

즉 맨 아래쪽에 있는 과자를 먹기 위해서 맨 아래쪽보다 위에 있는 과자들을 전부 빼내야 하죠

 

출처 https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

위 사진처럼 맨 위에 있는 데이터가 먼저 나가고 맨 밑에있는 데이터는 나중에 나가죠

다시 말씀드리자면 먼저 들어간 데이터는 나중에 출력되고 나중에 들어간 데이터가 먼저 출력 되는 구조입니다.

이런 구조를 흔히 선입후출(FILO) 또는 후입선출(LIFO)이라고 표현하기도 합니다.

2. DFS의 특징

---

1-1에서 말씀 드렸듯이 나중에 들어간 데이터를 먼저 처리하는 구조가 스택이라고 말씀 드렸죠?

DFS는 이와 같은 성질을 지닙니다.

 

저희가 서울에서 부산까지 갔다고 칩시다.

이때 저희는 왔던길을 체크하면서 갑니다.

 

그리고 부산에서 다시 서울로 올 때 왔던길을 다시 돌아온다고 치고 이때 왔던길에 체크되어 있던게

부산쪽에서 부터 지워진다고 생각해보세요

 

이해가 잘 되시나요?

 

위와 같은 예시처럼 먼저 들어간 데이터는 나중에 처리 되듯이 DFS는 스택 자료구조를 자주 사용하게 됩니다.

따라서 DFS를 사용할 때 스택 자료구조의 이해는 필수이죠

 

이런 형식을 사용할 때 반복문을 이용해서 구현할 수도 있지만 보통 재귀함수를 많이 사용합니다.

그래서 DFS를 사용하려면 스택과 재귀 둘다 능숙하게 다룰 줄 알아야 합니다.

3. DFS 코드 예제 (C언어)

---

1 1 0 0 1 0 1
0 1 0 0 1 1 1
0 0 0 0 0 0 1
1 1 0 0 0 0 0
1 0 0 0 0 1 1
0 0 1 1 0 1 1
0 1 1 1 0 0 1

위와 같은 7*7 맵이 주어져 있을 때 0은 땅이고 1이 강이라고 칩시다

1은 서로 붙어있고 1의 바깥쪽은 항상 0이죠

이런 상황속에서 DFS를 사용하면 매우 쉽게 강의 갯수를 구할 수 있습니다.

 

#include <stdio.h>

# define WIDTH 7
# define HEIGHT 7

int map[WIDTH][HEIGHT], visited[WIDTH][HEIGHT] = {}, river = 0;

void	dfs(int y, int x)
{
    if (0 <= x && x < WIDTH && 0 <= y && y < HEIGHT)
    {
    	if (!visited[y][x] && map[y][x] == 1)
        {
            visited[y][x]++;
            dfs(y + 1, x);
            dfs(y - 1, x);
            dfs(y, x + 1);
            dfs(y, x - 1);
        }
    }
}

int main(void)
{
    for(int i = 0; i < HEIGHT; i++)
    {
        for(int j = 0; j < WIDTH; j++)
            scanf("%d", &map[i][j]);
    }
    for(int i = 0; i < HEIGHT; i++)
    {
        for(int j = 0; j < WIDTH; j++)
        {
            if (map[i][j] == 1 && !visited[i][j])
            {
            	dfs(i, j);
                river++;
            }
        }
    }
    printf("%d\n", river);  // 결과값 5
    return (0);
}

맵을 입력받고 맵을 전체 탐색을 하면서 현재 위치가 강이면서 아직 방문한 적이 없는경우

dfs함수를 호출하면서 강의 갯수를 카운트 해줍니다.

dfs는 재귀함수를 사용한다고 말씀 드렸죠?

 

그래서 dfs함수를 재귀함수로 사용하게끔 구현합니다.

현재 위치가 맵을 벗어나지 않았는지, 방문한적이 없는지, 강인지 이 삼박자만 맞는다면

현재 위치로부터 상하좌우 재귀함수를 호출하면 됩니다.

 

그러면 저희가 원하는 결과값 5가 출력되는것을 알 수 있습니다.

 

처음에는 어려우실 수도 있으시겠지만 이해하기만 하면 재귀함수를 다루는데 능숙해 질겁니다.

 

4. DFS 문제들 (백준)

---

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

1260번: DFS와 BFS

해설

 

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

2606번: 바이러스

해설 

 

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

1012번: 유기농 배추

 

해설 

 

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

2667번: 단지번호붙이기

해설

 

 

반응형