BFS DFS

1. 꼭필요한 자료구조 기초

탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 탐색 알고리즘 - DFS/BFS

DFS/BFS를 이해하려면 기초 자료구조인 스택과 큐와 재귀함수에 대한 이해가 필요하다.

자료구조(Data Structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조

스택(Stack)

선입후출(First in Last Out)구조 또는 후입선출(Last in First Out)구조 (박스 쌓기)

큐(Queue)

선입선출(First in First Out)구조 (대기 줄)

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조 사용

재귀함수(Recursive Function)

자기 자신을 다시 호출하는 함수

재귀함수를 문제 풀이에서 사용할 때는 재귀함수가 언제 끝날지, 종료 조건을 꼭 명시

컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용

2. 탐색 알고리즘 DFS/BFS

그래프(Graph)

노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다.

• 그래프의 탐색 - 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 두 노드가 간선으로 연결되있다 = 두 노드는 인접하다(Adjacent)

DFS(Depth-First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

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

BFS(Breadth First Search)

너비 우선 탐색이라는 의미, 가까운 노드 부터 탐색하는 알고리즘

최단거리문제에 사용

코딩테스트 중에 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각

출처

https://velog.io/@y1andyu/Data-Structure-7-%ED%81%90-%EC%8A%A4%ED%83%9D-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661
https://taehoon9393.tistory.com/65