DFS / BFS

DFS

깊이 우선 탐색

이론적으로는 Stack 구조를 사용

구현은 재귀 함수로 처리 하면 된다

(넣고 방문 안했으면 방문 처리 + 내 인접 Node를 재귀적으로 DGS)

=> 방문했으면 pass

=> 방문 안했으면 dfs(1) -> dfs(2,3,8) 이런 식으로

예제)) 얼음의 개수

+) 파이썬으로 구현하기 위해서는 재귀함수 반복제한을 해제해야 한다.

 

 

 

BFS

너비 우선 탐색

이론적으로는 Queue 구조를 사용

Queue를 선언하고

제일 첫번째 넣고 방문 처리

popleft()를 통해 뽑은 애의 하위 인자들 중 방문 하지 않은 애들 모두 append

Q가 빌 때 까지 반복