BFS/DFS
우선 백트래킹을 알기 전에 BFS/DFS 먼저 살펴보자
BFS
BFS는 너비 우선 탐색 알고리즘이다.
그 말은 즉 깊이가 아닌 너비 위주로 탐색한다는 뜻이다.
예시)
시작 위치 A 부터 D까지 방문하는데
방문 방법은 가장 오래된 주변 정점을 먼저 방문한다.
구현은 큐 자료구조를 사용하는 것이 적절하다.
DFS
DFS는 깊이 우선 탐색이다.
그 말은 즉 너비가 아닌 깊이 위주로 탐색한다는 뜻이다.
시작 위치 A 부터 F까지 방문하는데
방문 방법은 가장 최근의방문 정점에 인접한 주변정점을 먼저 방문한다.
구현은 스택 자료구조를 사용하는 것이 적절하다.
구현 연습문제
https://www.acmicpc.net/problem/1012 (유기농 배추)
백트래킹
백 트래킹은 dfs/bfs와 유사하지만, 불필요한 부분은 탐색하지 않고 이전 단계로 돌아가서 다른 해를 찾는다.
구현 연습문제
https://www.acmicpc.net/problem/15649 (n과 m(1))
문제를 풀이 보면서 연습을 해보면 좋을 거 같다.
