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

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
• 대표적인 그래프 탐색 알고리즘으로는 dfs와 bfs가 있다.
• DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다.

스택 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.

-> 시간복잡도 O(1): 상수시간이다.

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다.
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있습니다.

-> 리스트를 활용할 경우 시간복잡도가 높아지므로 deque를 사용해주는 것이 좋다.

재귀 함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.
• 단순한 형태의 재귀 함수 예제
  • '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력합니다.
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
  

DFS

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 스택 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.
  • 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  • 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

BFS

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료궂를 이용하며, 구체적인 동작 과정은 다음과 같다.
  • 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  • 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.