코딩테스트에서 자주 쓰이는 알고리즘 중 하나입니다.
트리 구조에서 목표 노드까지 깊이 우선 탐색해 빠르게 목표 노드까지 갈 수 있는 알고리즘 중 하나죠
이와 비슷한 알고리즘 중 하나인 BFS란 알고리즘도 있는데 그 알고리즘은 너비 우선 알고리즘 으로써
큐 자료구조를 사용하고 DFS는 스택 자료구조를 사용합니다.
DFS는 일반적으로 재귀 함수를 이용합니다.
목차
- 스택 자료구조의 이해
- DFS의 특징
- DFS 코드 예제 (C언어)
- DFS 문제들 (백준)
1 스택이란?
스택(Stack)은 쉽게 프링글스 과자 통을 생각해 봅시다.
과자통이 있고 맨 위쪽부터 맨 아래쪽까지 과자가 들어 있죠
이 상황속 저희가 과자를 어떻게 먹죠?
위에서 부터 먹습니다.
즉 맨 아래쪽에 있는 과자를 먹기 위해서 맨 아래쪽보다 위에 있는 과자들을 전부 빼내야 하죠
위 사진처럼 맨 위에 있는 데이터가 먼저 나가고 맨 밑에있는 데이터는 나중에 나가죠
다시 말씀드리자면 먼저 들어간 데이터는 나중에 출력되고 나중에 들어간 데이터가 먼저 출력 되는 구조입니다.
이런 구조를 흔히 선입후출(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
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net