🩶 깊이 우선 탐색(DFS) — 한 놈만 끝까지 판다! (재귀함수가 일반적)

깊이 우선 탐색이란?

• 그래프 완전 탐색 기법 중 하나
  • 완전 탐색 : 그래프의 모든 노드를 탐색함
• 그래프의 시작 노드에서 출발 → 탐색할 한 쪽 분기 결정 → 최대 깊이까지 탐색 → 다른 쪽 분기로 이동 → 다시 탐색!

✅ 구현 시 재귀함수 사용 → 스택 오버플로에 주의! → 주의하랬는데 주의 안 해서 런타임 에러난 사람 여기있어요!

🩶 핵심 이론

노드 재방문 불가!

→ 방문 여부를 체크할 배열이 필요함

→ 그래프는 인접 리스트로

탐색 방식 : 후입선출(LIFO) → 스택

나동빈님 블로그 — 깊이 우선 탐색 (굳….!!!!!)

16. 깊이 우선 탐색(DFS)

BOJ 11724번 — 연결 요소의 개수 구하기

노드가 뭐죠? 엣지가? 뭐죠? 오! 그렇군요..

그래프 이론 - 노드(node), 에지(edge), 아크(arc)

내 풀이

[BOJ] 11724번 | 연결 요소의 개수 | C++

BOJ 2023번 — 신기한 소수

[BOJ] 2023번 | 신기한 소수 | C++

BOJ 13023번 — ABCDE

[BOJ] 13023번 | ABCDE | C++

🩶 너비 우선 탐색(BFS) — 맹목적인 탐색!

너비 우선 탐색이란?

• 그래프 완전 탐색
• 시작노드 출발 → 시작 노드 기준으로 가까운 노드 먼저 방문하며 탐색

✅ 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선해서 탐색
→ 목표 노드에 가는 경로가 여러 개 일 때 최단 경로를 보장한다! (오 좋네)

→ 최단 길이를 보장해야 할 때 많이 사용함 ( 미로찾기 등 )

준비물 : 큐 자료구조

BOJ 1260번 — DFS와 BFS

[BOJ] 1260번 | DFS와 BFS | C++