[이코테] Ch5. DFS/BFS

Ch5. DFS/BFS

1. 꼭 필요한 자료구조 기초

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

• 스택과 큐는 자료구조의 기초 개념
  • 삽입(push) : 데이터 삽입
  • 삭제(pop) : 데이터 삭제
• 오버플로 : 데이터가 꽉 찬 상태에서 삽입 연산 수행할 시 나타남
• 언더플로 : 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 나타남

1.1 스택

• 박스 쌓기와 유사
• 선입후출 구조 또는 후입선출 구조
• 가장 마지막에 들어온 데이터쪽부터 삭제되거나 추가

1.2 큐

• 대기 줄과 유사
• 먼저 온 사람이 먼저 들어갈 수 있으므로 ‘공정한’ 자료구조
• 선입선출 구조
• 가장 먼저 들어온 데이터쪽부터 삭제되거나 추가

1.3 재귀함수

DFS와 BFS를 구현하려면 재귀함수를 이해하고 있어야 한다.

재귀함수 : 자기 자신을 다시 호출하는 함수

• 재귀함수의 종료 조건
  • 재귀함수를 문제풀이에서 사용할 때는 재귀함수가 언제끝날지, 종료 조건을 명시해야한다. 그렇지 않으면 함수가 무한 호출된다.
• 재귀함수를 사용하면 코드가 간결해진다.
• 재귀함수는 수학의 점화식을 코드로 옮긴 것과 유사하다.

2. DFS

DFS : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

1. 그래프 방식
   • 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방식
     • 연결되지 않은 노드끼리는 무한의 비용이라고 작성
     • 실제 코드에서는 999999999 등의 값으로 초기화하는 경우가 많다.
     • 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 낭비
   • 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
     • 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
     • 연결된 노드만 저장하기 때문에 메모리를 효율적으로 사용
     • 인접 행렬에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
2. DFS 동작 과정
   1. 탐색 시작 노드를 스택에 삽입하고 방문처리
   2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
      1. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼냄
   3. a, b 과정을 더 이상 수행할 수 없을 때까지 반복
3. DFS 특징
   • 스택 자료구조에 기초해서 구현이 간단
   • 시간복잡도 : $O(N)$
   • 스택을 이용하기 때문에 재귀함수를 이용하여 구현하면 매우 간결하게 구현 가능

3. BFS

BFS : 너비 우선 탐색, 가까운 노트부터 탐색하는 알고리즘

• 큐 자료구조를 이용하여 구현하는 것이 정석

1. BFS 동작 방식
   1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
   2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
   3. a, b 과정을 더 이상 수행할 수 없을 때까지 반복
2. BFS 특징
   • 큐 자료구조에 기초해서 구현이 간단
   • deque라이브러리를 사용하는 것이 좋음
   • 시간 복잡도 : $O(N)$
   • 수행 시간이 DFS보다 좋은 편