🔧변경내용🔨
제목 날짜 내용 발행일 23.03.15
📌들어가기에 앞서
해당 포스터는 자료구조 학습 내용 중
DFS/BFS기초이론에 대한 내용을 정리한 것입니다.
-
그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문(탐색)하는 것이 목적
-
그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.
-
원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.
지하철 노선도를 보여주는 애플리케이션에서 경로를 탐색할 때는, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법이 있다.
그래프의 모든 정점 탐색 방법에도 여러 가지가 있다.
그중에서 가장 대표적인 두 가지 방법, BFS와 DFS를 알아보자.
이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.
📖 BFS(Breadth-First Search)
한국에서 미국으로 가는 비행기를 예약하려고 한다. 비행편에 따라 직항과 경유가 있다. 만약 경유하게 된다면, 해당 항공사가 필요로 하는 공항에 잠시 머물렀다가 가기도 한다. 경유하는 시간은 비행편마다 다르고, 경유지도 다르다. 이렇게 다양한 여정 중에서, 최단 경로를 알아내려면 어떻게 해야 할까
-
한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색
-
그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문
-
직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다.
-
경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다.
-
너비를 먼저 탐색하는 방법을
Breadth-First Search,너비 우선 탐색이라고 한다. -
주로 두 정점 사이의
최단 경로를 찾을 때 사용 -
만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다.
Q) 왜 최단 경로를 찾을 때 BFS 방식을 사용할까?
한 경로를 끝까지 모두 다 탐색하는 처음 발견한 답이 최단 거리가 아닐 수 있지만, BFS는 현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장이 되기 때문
📖 DFS(Depth-First Search)
그렇다면, 한국에서 출발하는 항공기의 모든 경로 중에 미국에 도착하는 여정을 알아내고 싶을 때는 어떻게 해야 할까
-
이때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야 한다.
-
DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다.
-
하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있다.
-
또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있다.
이렇게, 깊이를 먼저 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다.
한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다.
DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당하는 상황에 맞는 탐색 기법을 사용해야 합니다.
📖 Question
다음의 질문에 대한 답을 고민해 보자.
DFS와 BFS의 장단점은 또 무엇이 있을까?
깊이 우선 탐색의 장단점 (DFS)
장점:
최선의 경우, 가장 빠른 알고리즘이다. ‘운 좋게’ 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾는다.
단점:
찾은 해가 최적이 아닐 가능성이 있다.
최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸린다.
너비 우선 탐색의 장단점 (BFS)
장점:
최적해를 찾음을 보장한다.
단점:
- 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적일 수 있다.
- 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.
- 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.
그래프가 매우 크다면 어떤 탐색 기법을 고려해야 할까?
-
그래프 규모가 크다면 DFS 탐색을 고려해야한다.
-
재귀와 스택(stack)을 이용해 구현할 수 있다.
반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까?
-
그래프의 규모가 작고, depth가 얕으면 BFS 탐색을 고려해야한다.
-
BFS는 주로 queue(큐)를 사용해 구현한다.
-
BFS는 층별로 방문하여 탐색하기 때문에 선입선출 원리를 가진 queue를 이용하면 차례로 저장 후 꺼내서 탐색하기 유용하다.
📚 레퍼런스
코드스테이츠 수업자료
