[알고리즘] DFS/BFS: 그래프 탐색

기본개념

---

DFS/BFS

- 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 주로 다루고, 대표적인 탐색 알고리즘들이다.

 

자료구조(Data Structure)

데이터를 표현하고 관리하고 처리하기 위한 구조로 스택과 큐가 기초 개념

 

스택(Stack)

아래에서부터 위로 차곡차곡 쌓는 박스 구조, 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조

 

큐(Queue)

먼저 온 사람이 먼저 들어가게되는 공정한 대기줄 구조, 선입선출(First In First Out) 구조

 

재귀함수(Recursive Function)

자기 자신을 다시 호출하는 함수이며, 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다.

함수를 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

따라서 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현할 수 있다.

---

DFS(Depth-First Search)

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색, 스택 자료구조 이용

 

그래프 탐색

그래프는 노드(Node = Vertex:정점)와 간선(Edge)으로 표현되며 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다고 표현한다.

// 노드=도시, 간선=도로

그래프는 크게 두 가지 방식으로 표현할 수 있다.

1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식

2. 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

 

DFS 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리(처리된 노드가 다시 삽입되지 않게 체크)

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리, 없으면 최상단 노드 꺼냄

3. 2번의 과정의 더 이상 수행할 수 없을 때까지 반복

 

BFS(Breadth First Search)

너비 우선 탐색, 가까운 노드부터 탐색, 큐 자료구조 이용

 

BFS 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복