개발 공부 - DFS , BFS

 코딩 테스트 시에 열심히 나오는 DFS랑 BFS를 개념상 알아야 정확하게 짤 것 같아서 

코드 외 개념을 공부해 보았다.

1) DFS 

깊이 우선 탐색인데, 스택이나 재귀함수를 이용해서 짠다.

이거는 모든 노드를 방문해야 할 경우 사용한다.

(프로그래머스 코딩 테스트 할 때 자주 쓰면 코드 라인 수를 줄일 수 있다.)

제한이 있으면 가지치기, 백트래킹으로 경우를 줄일 수 있다.

만약에 재귀함수를 쓰면 종료조건 명시 안 하면 끝나지 않아서 오류난다.

   1

 2  3

45

같은 경우에는 1 -> 2 -> 4 - > 5 - > 3과 같이 간다.

근데 이거는 조건이 너무 많은 경우에는 그냥 생짜로 짜는게 복잡도가 덜 한 것 같다.

그치만 만약에 찾는 것이 깊숙히 있는 노드일 경우에는 유용하다. (맨 밑을 들어가서 보고 올라오니까...)

DFS로 짜놓고, 종료 되기 전에 조건문을 걸어서 반복문으로 넣어주는 부분이 가지치기라고 부르는 것인가 보다.

ㄴ 스택용 : 

2) BFS

너비 우선 탐색인데, 계층별로 탐색을 한다.

     1   

   2  3

  45 6 

7

같은 경우에는 1 -> 2 -> 3 -> 4 -> 5 -> 6 - > 7 같이 깊이 별로 탐색을 한다.

이거는 최단 경로 찾기, 인접한 노드 찾기 등에 사용된다고 한다.

이건 노드가 많고, 트리가 넓을 때 쓰면 아주 비효율적이라고 한다. 

(깊이 들어가면 메모리 입장에서는 별로임)

참조 : https://velog.io/@leobit/DFS-BFS-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking

https://europani.github.io/algorithm/2021/08/19/008-DFS-BFS.html

https://velog.io/@jieuihong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking-BFS-DFS