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)가 이루어짐
📍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)