DFS
Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 끝까지 완벽하게 탐색하는 방법이다.
Stack 혹은 재귀함수(Recursion)으로 구현된다.
재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.
경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
모든 노드를 방문하는 경우에 이 방법을 사용한다.
시간 복잡도 - 접점(V), 간선(E)
인접 리스트 : O(V + E)
인접 행렬 : O(V^2)
BFS
Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.
Queue를 사용해서 구현한다.
시간 복잡도 - 접점(V), 간선(E)
인접 리스트 : O(V + E)
인접 행렬 : O(V^2)
추가적으로 BFS로 효과적으로 풀 수 있는 문제들이 있다.
3가지의 조건을 만족한다.
-
최소 비용 문제
-
간선의 가중치가 1이다.
-
정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)
백준 문제
다음 내용
문자열
시뮬레이션
완전 탐색
재귀
이차원 배열
트리
다이나믹 프로그래밍
다익스트라/플로이드 워셜
부분 합
