DFS와 BFS C++로 구현해보자! (재귀, 스택, 큐)

1. 개념 이해하기

(1) DFS (Depth First Search)

DFS는 Depth First Search의 약자로, 말 그대로 깊이를 우선하여 탐색한다는 얘기이다.

아래 GIF 파일을 보고 쉽게 이해해보자.

DFS 작동 원리

1번 노드와 인접한 노드는 2, 5, 9 가 있는데 인접한 노드 중 숫자가 작은 곳 부터 들러보자.

2번 노드와 인접한 노드는 3이 있다. 바로 간다.

3번 노드와 인접한 노드는 4가 있다. 바로 간다.

더 이상 깊게 들어갈 수 없으니 바로 직전 노드인 3번 노드로 돌아간다.

3번 노드에서 가보지 않았던 더 깊은 노드가 없으므로 직전 노드인 2번 노드로 돌아간다.

마찬가지 이유로 1번 노드로 돌아간다.

이 때, 1번 노드에서 가보지 않은 더 깊은 노드가 있으므로, 그 중 숫자가 작은 5번 노드로 간다.

====이후 반복====

 

이런식으로 진행된다.

좀 더 규칙을 체계화해서 적어보면 다음과 같다.

1. 가보지 않은 더 깊은 노드가 있다면, 숫자가 작은 곳을 우선하여 방문한다.

2. 더 이상 가보지 않은 더 깊은 노드가 없다면, 이전 노드로 돌아간다.

3. 방문 가능한 모든 노드를 방문할 때까지 반복한다.

 

이전 하노이의 탑 포스팅에서 설명한 바와 같이, '자신의 축소 버전으로 자신을 재정의 가능한 함수'는 재귀적으로 표현 가능하다고 하였다. DFS는 재귀적으로 표현하기 아주 알맞은 알고리즘이다.

하지만 재귀적으로만 작성 가능한 것은 아니다! DFS를 STACK 자료구조를 사용하여 구현할 수 있다는 것은 굉장히 유명한 이야기이다.

 

아래는 스택 구조를 사용하여 DFS를 구현하는 방법에 대해서 설명하는 도식이다.

 

 

A가 push됨                                                                                                         B가 push 됨

D가 push 됨                                                                                                 더 깊은 노드가 없는 D를 pop함

E가 push 됨                                                                                            더 깊은 노드가 없는 E, B를 pop함

C가 push 됨                                                                                                        F가 push 됨

더 깊은 노드가 없어 F C A 순으로 pop 됨

 

위와 같이 나타낼 수 있겠다. 그림만 보면 간단한데 그래서 재귀 없이 결국 어떻게 구현을 하냐의 문제는 해당 포스트의 밑, 문제풀이 단락에서 직접 구현해두었다.

 

(2) BFS (Breadth First Search)

BFS는 Breadth First Search 의 약자로, 너비 우선 탐색이라고도 부른다.

DFS와 뗄레야 뗄 수 없는 쌍둥이와도 같은 녀석인데, 근본적으로 차이가 엄청나게 크다.

BFS는 뿌리부터 탐색을 시작해서, 뿌리와의 거리가 1인 노드를 전부 탐색한 후에 뿌리와 거리가 2인 노드를 전부 탐색하고, 이후 반복을 하는 형식이다. 때문에 뿌리 노드가 정해진다면 뿌리와의 거리가 최소인 노드를 찾는, 이른 바 최단거리 검색 문제 풀이에 아주 용이한 알고리즘이다.

BFS 작동 원리

 

원리적으로는 DFS보다 훨씬 이해하기 쉽다. 하지만 구현으로 가면 DFS보다는 살짝 난이도가 있게 느껴질 것이다. 왜냐하면 DFS는 재귀로 쉽게 구현이 가능하지만, BFS는 재귀적인 요소가 없기 때문에 보통 Queue 자료구조로 구현하게 된다. 위의 작동원리 GIF를 보면서 쉽게 설명이 가능하다.

 

작동원리 GIF에서 흰 색은 아직 가보지 않은 노드이며, 회색은 queue에 push된 노드, 검은색은 queue에서 pop된 노드를 의미한다.

시작 노드 a가 일단 push된다. Q={a}

a와 pop되고, a와 인접한 노드 b, c 가 push된다. Q={b,c}

b가 pop되고, b와 인접한 노드 d, e가 push된다. Q={c,d,e}

c가 pop되고, c와 인접한 노드 f, g가 push된다. Q={d,e,f,g}

====이후 반복====

 

이런식으로 진행된다.

좀 더 규칙을 체계화해서 적어보면 다음과 같다.

1. 첫 노드를 큐에 푸시한다.

2. 큐에서 pop하여 나온 값과 인접한 모든 노드를 순서대로 push한다.

3. 탐색이 끝날 때까지 2를 반복한다.

 

first in first out 원리에 의해, n층에서 pop된 노드와 인접하여 큐에 새롭게 push된 n+1층의 노드가, 이전에 이미 push되어있던 n층의 다른 노드보다 빨리 pop될 수 없다는 사실을 인지하면 쉽게 이해 가능한 내용이라고 생각한다.

 

이론적인 설명은 좋다. 그렇다면 C++ 코드로 실질적인 구현은 도대체 어떻게 하면 좋을까?

 

 

 

2. 구현 (feat 백준 문제풀이)

(1) DFS 구현 using 재귀 ( 백준 # 2667 )

백준 2667번 문제를 보자. 

백준 #2667 단지번호 붙이기

 

단지번호 붙이기 라는 제목과는 다르게, 실제로 번호를 붙일 필요는 없고 단지가 몇 개인지와 각 단지 당 아파트가 몇 채씩 있는지를 묻고 있다. 위와 같이 2차원 맵(지도)가 주어지고 분리된 공간의 개수를 세는 종류의 문제가 나오면 DFS가 굉장히 유효하다. 아이디어는 아래와 같다.

 

메인 아이디어

맵의 모든 좌표에 대해서 탐색을 할거다. 각 좌표에 대해서 모든 인접한 집을 DFS를 통해서 탐색할 것이다. 더 이상은 탐색할 수 없을 때까지 탐색하고 나면, 해당 좌표와 인접한 모든 구역이 탐색되었을 것이다. 이 집들은 모두 같은 단지에 속하게 된다.

 

이후로도 탐색을 계속해서 하긴 할건데, 아래와 같은 경우에는 할 필요가 없다.

1. 집이 없는 곳

집이 없는 곳이면 애초에 어느 단지에 속할 수가 없으니, 탐색할 필요가 없는 것이다

2. 이미 탐색된 적이 있는 곳

탐색된 적이 있다면, 그 집은 이미 다른 단지에 속해있다는 얘기가 된다. 예를 들어 백준 예시그림을 보면 (1,0) 지점을 DFS하여 이미 1단지가 전부 탐색된 상태라고 하자. 이때 (2,0)은 탐색된 적이 있는 것으로 기록될 것이고, 실제고 1단지에 속하기 때문에 구태여 다시 탐색할 필요가 없어진다.

 

이런식으로 모든 좌표에 대해서 위의 두 조건을 제외한 경우에 전부 DFS를 진행해줄건데, 해당 횟수만큼이 단지의 개수가 된다는 것은 쉽게 생각해볼 수 있을 것이다.

우리는 단지의 갯수 뿐 아니라 각 단지에 속하는 집의 수도 같이 세어줘야 한다.

재귀를 이용한 dfs 구현

집의 위치가 (x,y)라고 해보자. (x,y)에 인접한 위치는(x+1,y), (x-1,y), (x,y+1), (x,y-1)의 네 곳이 있다. 네 곳에 대해서 각각 탐색 가능한 조건에 부합한다면, 해당 좌표에서 또 다시 dfs를 진행할 것이기 때문에 네 곳을 모두 파악해줘야한다.

하지만 하드코딩을 하게 되면 내가 뭘 썼는지도 알아보기 힘들게 될 것이다.

따라서 dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0} 을 미리 선언해둔다면 nx=x+dx[i], ny=y+dy[i]를 했을 때 위의 4종류의 좌표 모두를 간략하게 표현 가능한 것이다. 참고로 0, 1, 2, 3 순서대로 동서남북이 된다. (x축을 세로 y축을 가로로 두고 푸는 경우)

isValid 함수는 앞서 메인 아이디어에서 설명했던 두 조건에 해당하면 false를 return하게 되어있다. 이 때 한 줄이 더 적혀있는데, 이건 범위 안에서 탐색을 진행시키기 위한 제한사항이라고 보면 된다. 이동할 예정인 장소가 지도의 한계를 넘어가면 당연히 오류가 생기지 않겠는가?

 

또한 dfs 함수가 int함수가 되게 하고 위와 같은 리턴값을 가지게 한다면, 단지가 가진 집의 개수를 최종적으로 리턴하게 된다.

 

최종코드(1)

최종코드(2)

맞았습니다!!

 

DFS 구현하는 방법만 안다면 그렇게 어렵지 않은 문제였다.

 

(2) DFS 구현 using 스택 ( 백준 # 2606)

백준 2606번 문제를 보자.

백준 #2606 바이러스

 

1번 컴퓨터와 인접한 모든 컴퓨터의 개수를 구하는 아주아주아주 간단한 DFS 문제이다.

사실은 DFS를 계속해서 재귀로만 풀다가, 스택으로도 구현하는 방법이 알고싶어졌기 때문에 직접 시도해본 첫 문제이다.

내 나름대로 정의에 완벽하게 부합하게 코드를 만들어보았다.

정말 간단한 문제이므로 아이디어에 대한 설명 없이 바로 코드 설명으로 들어가도록 하겠다.

 

최종코드(1)

최종코드(2)

스택을 사용하여 DFS를 구현한 방식을 주목해주었으면 좋겠다.

스택을 사용한 DFS의 구현

sp의 위치를 시작노드로 하는 DFS를 수행하는 함수이다.

우선 시작노드를 스택에 넣고 시작한다.

현재 위치는 항상 스택의 탑에 있는 노드이다.

또한, 항상 현재 노드와 인접한 노드 중, 방문된 적 없는 노드만을 방문할 것이다. 해당 조건이 만족하는지의 여부는 isValid 함수를 통해 알려주도록 구현하였다.

인접한 모든 노드 중에 방문된 적 없는 노드를 발견한다면 해당 노드를 스택에 push하고, break로 for문을 탈출해줘야한다. 왜냐하면 탈출하지 않는 경우 가능한 모든 노드를 스택에 넣게 될 것이기 때문이다. BFS의 구현이 아니기 때문에 이러한 방식을 사용해서는 안된다.

 

여기서 DFS를 원리대로 구현하기 위해 정말 중요한 변수가 isDeapest 변수이다.

우선 인접한 노드를 탐색하기 전에 isDeapest 변수를 true로 설정해준다.

인접한 모든 노드를 탐색하는 과정에서 만약 탐색 가능한 노드가 존재했다면 isDeapest 변수를 false로 바꿔준다.

하지만 만약 그런 노드가 존재하지 않았다면... for문이 완료한 후에도 isDeapest가 그대로 true로 남게 될 것이다. 현재 있는 노드가 탐색 가능한 가장 깊은 노드라는 것을 의미한다.

이런 경우 현재 노드를 pop해줌으로써 위의 노드로 돌아가주는 것이 중요할 것이다.

 

결과적으로 이렇게 구현하게 되면 가장 깊은 노드까지 들어왔다면 pop되고 이후 탐색이 진행되는, 우리가 바라던 DFS가 스택 없이 완벽하게 구현되게 되는 것이다.

맞았습니다!!

결과는 역시 맞았습니다!!

 

(3) BFS 구현 using 큐 ( 백준 # 7576 )

백준 7576번 문제를 보자.

 

백준 #7576 토마토

 

텍스트의 압박이 굉장하다. 참을성을 가지고 열심히 읽어주길 바란다.

요컨데, N*M 격자의 박스에 익은 토마토, 안 익은 토마토, 빈 칸이 배치되어 있는 상태가 주어졌다고 하자.

익은 토마토와 인접한 안 익은 토마토는 다음날 익는다고 하면 최소 며칠만에 모든 토마토가 익겠냐, 하는 희한한 문제이다.

 

익은 토마토는 0일만에 익을 것이고, 안 익은 토마토는 익은 토마토와의 최단거리 만큼의 일수가 지난 후에야 익을 것이다.

익은 토마토와의 최단거리가 3칸이라면 3일만에 익는다는 얘기다. 아까도 설명했지만, 최단거리를 구하는 문제에서는 BFS가 굉장히 강력하다.

 

이 때 주의할 점은 익은 토마토가 여러 개 들어갈 수 있다는 점이다. 필자는 처음 이 문제를 풀 때는 모든 익은 토마토를 기준으로 하여 각 토마토의 좌표로부터 BFS를 전부 실행하여, 결과값의 최솟값을 취하는 방법을 선택했었으나, 해당 방식으로 문제를 풀었을 때 시간 초과라는 벽에 부딪히고 말았다. 스스로 만든 고정관념에 갖혀있었기 때문이라고 볼 수 있는데, BFS의 시작노드를 하나로 할 필요가 없다는 사실 역시 굉장히 중요하다. 그냥 익은 토마토를 전부 큐에 넣고 BFS를 시작하면 쉽게 결과가 구해진다.

 

Queue 자료구조를 통한 BFS의 구현

큐가 비어있지 않다면, 우선 pop을 한 후, pop된 노드와 인접한 모든 탐색 가능한 노드를 큐에 넣어주면 된다.

탐색 가능 여부는 역시 isValid 함수가 알려줄 것이다. (DFS 문제 풀이 참고)

큐가 빌 때까지 해당 과정을 반복하면 BFS가 완료되는 것이다.

난이도 체감은 재귀를 이용한 DFS 구현보다는 어렵고 스택을 이용한 DFS 구현보다는 쉽게 느껴진다고 평가할 수 있겠다.

 

최종코드(1)

최종코드(2)

 

isPossible 함수는 BFS가 완료된 후에도 안 익은 토마토가 존재한다면 false를 반환한다.

max_date 함수는 BFS 완료 후 익기까지 가장 시간이 오래 걸리는 경우의 일 수를 반환해주는 함수이다.

맞았습니다!!

맞았습니다!!

 

 

 

3. 고찰

DFS, BFS 문제를 풀어봤는데 상당히 재미있었다. DFS BFS 알고리즘을 구현하는 방법을 익히기 전에 이러한 문제들을 봤을 때는 어떻게 풀지 감이 잘 안잡혔는데, 몇 문제 풀어보니까 감이 잡혀온다.

BFS 문제의 경우 시작노드를 여러 개 집어넣고 시작해도 문제가 발생하지 않는다는 점을 유념하면서 문제를 접해야 한다.

 

한 가지 해결되지 않은 의문점은 DFS를 구현함에 있어 재귀와 스택 중 무엇이 더 좋은가에 대한 것이다. 단지번호붙이기 같은 문제는 int 함수를 통해 단지에 속하는 집의 수를 쉽게 구할 수 있기 때문에 재귀함수가 확실히 편했다. 하지만 바이러스의 문제가 스택으로 풀었을 때의 장점을 가지고 가는지는 사실 잘 모르겠다. 재귀함수로 짜도 크게 다르지 않았을 것 같다.

다만 깊이가 깊어진다면 스택을 사용하는 것이 더 유리할 것으로 생각되어지기는 한다. 어느 수준 이상의 깊이에서 이러한 차이가 발생하는지도 지속된 공부를 통해 알아가보는 것이 좋을 것 같다.

 

 

 

 

Sources

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

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

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

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

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

2667번: 단지번호붙이기

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

2606번: 바이러스

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

7576번: 토마토