깊이 우선 탐색 (DFS : Depth-First Search)

이미지 출처

설명

루트 노드(사진상 1번 노드)에서 시작해서, 하나의 분기(branch)가 끝날 때까지 탐색 후 다음 분기로 넘어간다.
(== 끝을 볼 때까지 일단 냅다 하나씩 해본다.)

장점

1. 구현이 쉽다
2. 최선의 경우 빠르다

단점

1. 최악의 경우 느리다.
   (성능이 보장되지 않음)
2. 구한 경우가 최적을 보장하지 않는다
   : 구한 경우의 수가 항상 최적의 해(최단거리)를 의미하는 것은 아니다.

여기서 만약에 모든 경우의 수를 구하는 문제가 아니고,
분기 중에 아니다 싶으면(원하는게 나올 가능성이 없는 경우) 포기해야 하는 경우가 있는데,
이 때 활용해야 하는 알고리즘은 백트래킹이다.

구현

재귀함수나 stack을 이용해서 구현할 수 있다.

활용해야 하는 상황

모든 노드를 방문해야 하는 상황
가중치가 있는 상황

관련 문제

프로그래머스 Lv2 타겟 넘버
프로그래머스 Lv3 네트워크
백준 실버3 바이러스

---

너비 우선 탐색 (Breath-First Search)

이미지 출처

설명

루트 노드(1번)에서 시작해서 인접한 노드를 먼저 탐색한다.

장점

1. 무조건 최적의 해를 보장한다.

단점

1. 경로가 길면 메모리가 많이 필요하다

구현

Queue를 이용하여 구현한다.
시작노드 Push, 탐색체크
Pop한 다음
아직 탐색하지 않은 인접 노드들을 Push, 탐색체크

이렇게 Queue내내 하고 나면
전체 노드들을 인접한 순서대로 탐색할 수 있다.

활용해야 하는 상황

최 단 거 리

관련 문제

프로그래머스 Lv2 게임 맵 최단거리

---

참고
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
https://wikidocs.net/123116