[DFS/BFS] 그래프 탐색 알고리즘

https://youtu.be/7C9RgOcvkvo?si=RF2LuZTkoj4NQeAy

본 내용은 위 유투브를 참고해서 작성했습니다!

---

그래프 탐색 알고리즘: DFS/ BFS

• 탐색 (Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘: DFS, BFS
• 코딩테스트에 매우 자주 등장하는 유형

 

스택 자료 구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)
• 입구와 출구가 동일한 형태
• 박스, 프링글스 과자통 등
• 파이썬에서는 리스트로 스택을 사용할 수 있음. -> append(n), pop()
  • 순서를 뒤집어서 출력할 때는 [::-1]
• 자바에서는 peek()라는 메소드를 사용함. 

 

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식 (선입선출)
• 입구와 출구가 모두 뚫려있는 터널 형태
• 파이썬: deque라이브러리를 사용해야 함. (시간 복잡도가 줄어듦) -> append(), popleft() 
  • deque는 스택과 큐 라이브러리를 모두 활용할 수 있음. 
  • 역순으로 출력하려면 reverse()
  • 리스트보단 deque를 이용하는 것이 훨씬 시간적에서 효율적임
• 자바에서는 offer와 poll 메소드를 사용함.