내일배움캠프 99일차 - 자료구조 & 알고리즘 19주차 : BFS, DFS

DFS / BFS

DFS(깊이 우선 탐색) - 한 길로 끝까지, 막히면 되돌아온다.

DFS 방문순서: 0 → 1 → 3 → 5 → 4 → 2

방문 규칙

1) 현재 위치를 방문 표시(visited) 한다.
2) 안 간 이웃이 있으면 깊이 내려간다.
3) 더 갈 곳이 없으면 한 단계 되돌아온다.

생명선 - 방문 체크(visited)

만약에, "방문 표시"를 하지 않는다면?
 : 0에서 1로 간 뒤, 1의 이웃인 0으로 다시 가게 된다.

0 → 1 → 0 → 1 → … 영원히 반복

현실의 

BFS(너비 우선 탐색)

파동처럼 모든 길을 한걸음 씩 번갈아 움직여 체크하는 방식.