PS를 하며 느끼는 DFS와 BFS 선택의 기준

알고리즘 문제 풀이를 하며 여러 사람들과 이야기를 나눈적이 있다.

그 중 알고리즘 문제 풀이를 막 시작한 초급자분들이 가장 헷갈려하는 부분이
그래프탐색 문제를 만났을때, 언제 DFS를 선택해야되고 언제 BFS를 선택해야 되나요? 에 대한 부분이였던것 같다.

보통 코딩테스트 문제를 풀며 느끼는 이런 그래프 탐색 문제의 경우

1) DFS or BFS 어떤것이든 사용해도 무관한 경우
2) DFS를 사용하는것이 압도적으로 편한경우
3) BFS를 사용하는것이 압도적으로 편한경우

이렇게 3가지 경우의 수로 나뉘는것 같다.

나는 1) 의 경우 DFS를 선호하는경향이 있다. 이건 본인이 어떤 알고리즘을 더 편하게 느끼고 많은 경험이 있는지 판단해 적당히 정하면 될 문제라고 생각한다.

그렇다면 남은 문제는 2)번과 3)번을 구분짓은 기준인데
코딩테스트에 정말 높은 빈도로 나오는 그래프탐색 알고리즘. 과연 언제 DFS를 사용하고 BFS를 사용해야될까?
(이 글은 DFS와 BFS에 대한 기초지식이 있음을 가정하고 작성하였다.)


🟦 한눈에 보는 DFS 와 BFS알고리즘의 동작 방법

일단 그림으로 어떻게 돌아가는지에 대해 간략하게 알아보기로 하자



# DFS

첫번째로 DFS의 동작 순서이다. 재귀적인 특징으로 구현을 한다.
DFS는 깊이 우선탐색 알고리즘으로서 우직하게 선택한 한 루트를 파고든다.위 그림에서 예를 보면 0 > 1 루트를 선택했기때문에 우직하게 1번 노트에서 파고들 수 있는 2번 노드로 이동을 한다.

#BFS

그다음은 BFS알고리즘이다. 큐를 사용해서 탐색을 관리한다.
DFS와 다르게 0번노트에서 시작시 0번에서 갈 수 있는 모든 노드를 1번의 "턴"에 탐색한다.
여기서 말하는 턴이란 흔히 말하는 depth(깊이) 라고 보면 될 것 같다.
위 그림에서 볼 시 2, 3, 4 번의 과정을 묶은것이 한 턴으로 보면 될 것 같다.

위 움짤을 보면 확실히 DFS와 BFS는 서로 다른 탐색의 절차를 갖는다는것을 확인할 수 있다.



🟦 그렇다면 DFS와 BFS를 선택함에 있어 어떤 기준이 필요할까

내 개인적인 경험으로(나는 DFS를 더 자주 사용한다) 대부분의 경우 DFS와 BFS 어느것을 선택해도 무방한 문제들이 많다. (필자가 경험한 코딩테스트 수준의 알고리즘)

나는 보통 DFS는 재귀적인 특징과 백트래킹을 이용한, 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제를 풀때 선호하고(대표적으로 조합 순열 구현)
BFS는 depth(깊이)특징을 이용한 문제(대표적으로 최단경로)를 풀어야할때 선호한다.




🟦 DFS를 이용한 순열, 조합 구현

정말정말 코딩테스트에 자주 나오는 기술이다.

사실 파이썬이나 뭐 여러 언어에는 자체적으로 내장된 순열 조합 라이브러리가 있다. 하지만 삼성테스트의 경우 내장 라이브러리를 사용하지 못 하게 하는 경우가 있어 구현법을 숙지해야될 필요성이 있기도하고
단순 순열,조합 라이브러리를 쓰기엔 경우를 선택하는 분기를 순열,조합을 구성할때 넣어줘야 되는 경우가 있기 때문이다.

위 사진은 숫자의 조합을 구현하는 로직을 담은 트리이다.
각 숫자를 선택할때 왼쪽 노드로 이동시 선택하고
오른쪽 노드로 이동시 선택하지않는다.

선택이라는 관점에서 본다면, 내가 선택한 분기의 끝까지 진행시 조합의 한가지 경우의 수를 얻을 수 있다.
루트 노드를 기준으로 발산 하며 하나하나 모든 경우의 수를 탐색하는 것이다

아래 링크를 참조하면 C++로 작성한 조합과 순열을 구하는 DFS로직 코드를 볼 수 있다. 코드를 보고 이해하는 편이 조금 빠를것같다는 생각?

https://foameraserblue.tistory.com/62?category=481823
https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

https://yabmoons.tistory.com/100

[ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++)

### 위의 예를 보기위해 DFS와 재귀적 개념, 그리고 백트래킹 알고리즘에 대한 추가적인 지식이 필요할 수 있다.
https://blog.naver.com/kks227/220786417910

백트래킹(Backtracking) (수정 2019-10-09)

위 블로그에서 정말 설명을 잘 해주셨다 참고하자.


🟦 BFS를 이용한 최단경로 탐색

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

2178번: 미로 탐색

정말 DFS와 BFS선택이 극명하게 나뉘는 문제중 쉽고 가장 이해하기 쉽다고 생각한다.
위 문제의 해설을 잠시 봐보자.

분홍색 타일이 출발점이고 파란색 타일이 도착점이라고 가정을 해보자.

BFS의 경우 뎁스에 따라 갈 수 있는 모든 노드를 너비 우선 탐색한다.
위 사진에서 노란 타일의 진행 과정을 보면 이해가 쉬울것이다.
파란타일에 도착했을때 기록된 이동 횟수가 목적지로 이동한 최소 횟수가 된다.




만약 이 상황에서 DFS를 사용한다면 어떻게될까
단순하게 모든 경로를 탐색한다음 도착점에 도착했을때 가장 적은 칸 수를 이동한경우를 구하면 되는거아님? 이라고 생각할 수 있는데.....

만약 DFS 진행시 첫번째 한 분기에서 이런 경로로 진행을 했다고 가정해보자.
일반적인 DFS구현에서는 한 번 방문한 노드를 재방문 하지 않기위해 visit 배열이나 기타 방법으로 방문한 적이 있음을 표시한다.

빨간경로로 이동 한 후 한 분기에 따라 파란경로로 이동을 하려 한다 생각해보자.

위 사진에서 볼 경우 기존에 빨간선으로 이동한 경로는 모두 visit처리가 되어있다.
즉 다음 분기에 어떤 경로로 깊이 우선탐색을 할진 모르겠으나
이미 이동했던 타일로는 이동을 할 수가 없다.(이동을 할 수 있게 매번 방문여부를 초기화한다던가의 처리를 하라면 할 수 는 있겠지만 무척 복잡해지며 제대로 작동할수 있게 코드를 짜는게 무척 어렵거나 불가능할것이다)

설명이 이해가 잘 안될 수 있다. 쉬운문제니 직접 DFS로직으로 문제풀이를 시도해보자.



# 사진출처
https://blog.naver.com/kks227/220785747864



🟦 결론

결론은 간단하다 사실 문제를 많이 풀어보면 문제만 봐도 DFS인지 BFS인지 감이 온다.
하지만 일단은 알고리즘 풀이에 입문하신 분을 기준으로 설명한 글이기때문에 정말 간단히 정리해보자면

DFS
1) 연결된 그래프를 완전 탐색하는데 활용가능
2) 모든 경우를 하나하나 다 탐색을 해야될경우 이용(위의 예의 경우 조합, 순열 모든 경우의수를 하나한 다 찾고자할때)
3) 위의 개념과 결부된 깊이 우선탐색이라는 개념을 가진 순열, 조합 구현에 활용

BFS
1) DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
2) depth(깊이)를 계산해야되는 문제에 활용(위의 문제예의 경우 최단경로의 길이 == depth(깊이))
3) 위의 개념과 결부된 가중치가 같은 그래프에서 최단거리를 찾는데 활용




근데 저 최단거리라는말 어디서 들어본적 있지 않나요?
그래프 최단거리를 간다는 말은 사실 최단경로를 가는 경우와 거의 동치의 단어이다.

우리가 보통 배우는 최단경로 알고리즘 하면 딱 떠오르는 다익스트라, 플로이드 와샬 알고리즘!
위와 같은 이유로 사실 다익스트라 문제들 풀이를 보면 특정상황에 한정한 경우지만
BFS로 푼 풀이가 심심찮게 올라온다

BFS알고리즘의 파생형 알고리즘은 0-1 BFS알고리즘도 존재한다.
특정상황에 최단경로를 효율적으로 찾을 수 있게 도와주는 알고리즘이고
실제 PS 최단경로 문제 풀이시 많은 횟수로 사용되는 알고리즘이다.
https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/

[그래프] 0-1 BFS 알고리즘

https://nicotina04.tistory.com/168

0-1 BFS(0-1 Breadth First Search)

관심있으면 추가로 공부 해보시길 ㅎㅎ