BFS, DFS

 

완전 탐색 기법 중에는 BFS/DFS 알고리즘이 있다.

 

코딩 테스트 문제에서 자주 만나게 되는 알고리즘 카테고리이다.

그렇기 때문에 문제를 풀기 전에 개념을 세우는 것이 가장 중요하다.

 

개념을 공부하기 전에 그래프/트리, 스택/큐 자료구조에 대해 알고 가자.

 

 

 

📍그래프란?

: 정점(Node)와 정점을 연결하는 간선(Edge)로 이루어진 자료구조

: 순환 싸이클이 있을 수도 있고, 없을 수도 있다.

 

◾정점: A, B, C, D, E

◾간선: 정점을 이어주는 선(왼쪽의 경우 6개의 간선으로 이루어짐)

 

 

 

 

 

📍트리란?

: 순환 싸이클이 없는 그래프를 의미한다.

 

 

 

 

 

 

---

 

 

 

 

📍스택이란?

: 데이터를 기록하는 구조이다.

→ LIFO(Last Input First Out)

→ push: 가장 먼저 입력된 데이터가 가장 밑에 쌓인다. (차곡차곡 쌓음)

→ pop: 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다.

 

 

 

 

📍큐란 무엇인가?

: 스택과 같은 데이터 기록 구조이지만 입출력 형식이 다르다.

→ FIFO(First Input First Out)

→ 가장 먼저 입력된 데이터가 먼저 삭제된다.

→ 한쪽 끝에서만 삽입(Enque)이 이루어지고, 다른 한쪽 끝에서만 삭제(Deque)가 이루어짐

 

 

 

 

---

 

 

 

 

출처 https://covenant.tistory.com/132

 

📍DFS(깊이 우선 탐색)

: 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

→ 스택 또는 재귀함수로 구현

→ 이동할 때에 가중치 또는 제약이 있는 경우 사용

 

 

📍BFS(너비 우선 탐색)

: 루트 노드에서 인접한 노드를 먼저 탐색한다.

→ 큐로 구현

→ 최단 거리 문제를 풀 때 사용

 

 

 

 

 

 

 

 

 

 

참고

 

스택 이미지: https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

큐 이미지: https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)