[알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조

 

본 알고리즘 포스팅의 주제인 DFS와 BFS 알고리즘에 대해 알기전에,

 

먼저  '그래프 탐색'이란 무엇인가에 대해서 알아보는 것이 필요하다. 

(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)

https://www.youtube.com/@dongbinna

동빈나

 

 

---

 

 

그래프 탐색 이란?

우선 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 

 

그래프에서의 탐색은 하나의 노드를 시작으로 연결된 모든 노드들을 모두 찾는 과정을 말한다. 

 

 

다음으로 DFS와 BFS에 대해 다루기 전에 '스택'과 '큐'라는 자료구조에 대해 정리해보았다. 

 

 

 

 

 

 

 

1. 스택 자료구조 란?

먼저 들어 온 데이터가 나중에 나가는 형식,

즉 선입선출의 자료구조를 스택 자료구조라고한다. 

 

박스 쌓는 상황을 그 예시로 생각하면 이해하기 쉽다. 

 

 

 

 

 

위의 그림처럼 아래에서부터 박스를 쌓고, 꺼낼때는 위의 박스부터 꺼내는 것처럼

스택 자료구조는 먼저 들어 온 데이터가 아래에 쌓여있기 때문에

가장 나중에 나가게 된다. 

 

 

 

 

 

 

 

2. 큐 자료구조 란?

큐 자료구조는 위의 스택 자료구조와는 반대로

먼저 들어 온 데이터가 먼저 나가는 형식,

즉 선입후출의 자료구조를 큐 자료구조라고 한다. 

 

 

입구와 출구가 모두 뚫려있는 터널과 같은 형태를

데이터들이 지나간다고 시각화하여 생각하면 이해가 쉽다. 

 

 

 

---

 

 

 

다음 포스팅에서는 본격적으로

DFS에 대해서 다뤄보도록 하겠다. 

2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘

[알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘