BFS/DFS 공부 메모

간선 정보를 저장할 때는 두가지를 이용하여 저장할 수 있다.

  1. 인접행렬

      공간 복잡도 O(V^2)

      간선 유무 확인 시간 O(1)

  2. 인접리스트

       공간 복잡도 O(V+E)

       간선 유무 확인 시간 O(1) (x)       

 - BFS는 현재 정점에서 가장 가까운 곳부터 차례대로 탐색을 해나가는 너비우선탐색

  Queue를 사용

  기준점으로부터 가까운 곳부터 간다.

  최적의 해를 구하라

 - DFS는 현재 정점부터 갈 수 있는 곳까지 파고 들어 탐색하는 깊이우선탐색

  Stack(또는 재귀)을 이용

  백트레킹에 유리

DFS/BFS를 사용하면서 조심해야할 것 : 이미 방문한 정점에 다시 갈 수 있으니 visited 배열을 만들어 체크해야한다.