[FE - ConnecTo] DAY46 TIL👩🏻‍💻

22.09.15 스스로 공부한 내용들을 정리하였습니다 😊
피드백은 언제나 환영입니다! 🍊

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법이며, 최적화 문제와 결정 문제를 푸는 방법이 될 수 있음.

코딩에서는 반복문의 횟수까지 줄일 수 있기 때문에 효율적임. 이를 가지치기라고도 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미임.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어서 경우의 수가 줄어들지만, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것으로,
답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것이라고 생각하면 됨.

---

DFS(Depth First Search)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 가능한 모든 경로(후보)를 탐색하는데, 불필요할 것 같은 경로를 사전에 차단하는 등의 행동이 없기 때문에 경우의 수를 줄이지 못함.

✅ 구현 방법

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더이상 수행할 수 없을 때 까지 반복한다.

---

BFS(Breadth First Search)

그래프에서 가까운 노드부터 탐색하는 알고리즘.

✅ 구현 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

---

📍출처

• https://chanhuiseok.github.io/posts/algo-23/
• https://velog.io/@falling_star3/2.-깊이우선탐색DFS과-넓이우선탐색BFS