BFS, DFS

BFS는 Breadth-First Search로 너비 우선 탐색, DFS는 Depth-First Search로 깊이 우선 탐색을 말하다. 두 탐색법은 모두 그래프에서 사용하는 방식이다. 이를 좀 더 자세히 알아보자

그래프, 트리

그래프를 간단히 말하자면 정점(Node)와 간선(Edge)들로 이루워진 자료구조의 일종을 말한다. 여러 종류들의 그래프가 있으나 그 중 가장 친숙한 것은 아마 "트리"일 것이다. 트리는 그래프의 한 일종이며 부모와 자식의 계층을 갖는 자료구조를 말한다. 여기서는 깊게 다루지 않겠다.

그래프의 탐색

이러한 그래프를 탐색하고자 할 때가 있다. 여기서의 탐색이란 하나의 정점에서 시작하여 그래프의 다른 모든 정점을 한번씩 방문하는 것을 말한다. 왜냐하면 그래프의 경우 배열과 같이 정렬되어 있지도 않고, 따라서 특정한 값을 찾기 위해서는 모든 Node를 직접 방문해야 하기 때문이다.
아무튼 이러한 목적을 갖고 그래플르 탐색하는 방법의 가장 대표적인 두가지 방법이 바로 BFS와 DFS이다.

BFS - 너비 우선 탐색

임의의 노드에서 시작하여 인접한 노드를 먼저 탐색해 나가는 방법이며, 시작 지점에 가까운 노드들을 먼저 탐색하게 된다. 일반적으로 특정한 노드나 값, 상태에 최단 거리로 도달하는 경로를 찾을 때 사용하게 된다. 그래프를 생각해본다면 시작 노드의 인근 노드를 전부 먼저 탐색한 후, 해당 노드들의 인근 노드들을 다시 모아 재차 탐색하는 형식이 될 것이다.

이를 코드에서 구현하기 위해서는 Queue를 사용하면 된다. 노드를 탐색하고, 자신과 인근한 노드들을 queue에 넣어 주는 형태로 탐색을 하면 쉽게 구현할 수 있다.

DFS - 깊이 우선 탐색

임의의 노드에서 시작하여 진행할 수 있는 끝까지 탐색을 하고 다시 돌아와 다음 선택지를 탐색하는 것을 말한다. 쉽게 설명하자면 길을 가다 여러 갈림길이 있을 때, 한 쪽으로 끝까지 가서 그 끝을 확인 한 후 다시 갈림길로 돌아와 다른 길을 선택하는 경우를 말한다. 일반적으로 A -> B 로의 경로에 있어서 그 경로의 특징(루트 or ?)을 기록하거나, 조건이 존재할 때 사용한다.

이를 코드에서 구현하기 위해서는 Stack이나 재귀함수를 사용하면 된다. stack을 사용할 경우 해당 노드를 탐색하며 나오는 인접한 노드들을 Stack에 넣어주며 진행하면 된다.(이때 순서를 헷갈릴 수 있으니 구현하고 직접 확인해 보자.) 두 번째 방식인 재귀함수를 이용하는 편이 좀 더 편리할 때가 많다. 재귀함수 내부에서 visited와 adjs(인접 리스트 or 맵)를 가지고 현재 노드에 근접한 노드에 대해서 다시 재귀함수를 부르는 식으로 말이다.

연습

실제로 코딩테스트 문제를 풀어보며 연습해보는 것을 추천한다.
나도 후에 해당 문제들을 다시 풀어보려 한다.
https://school.programmers.co.kr/learn/courses/30/parts/12421