[2021 이코테] 3. DFS & BFS

https://www.youtube.com/watch?v=7C9RgOcvkvo 

---

0. DFS/BFS

• 그래프 탐색 알고리즘
• 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터 찾는 과정

---

1. 스택과 큐 자료구조

(1) 스택 자료구조

• 선입후출
• 입구 = 출구
• 스택 구현 예제
  • append(): 삽입
  • pop(): 삭제

(2) 큐 자료구조

• 선입선출
• 입구와 출구가 모두 뚫린 터널 형태
• 큐 구현 시 list가 아닌 deque를 이용할 것 => 시간복잡도 때문
• 큐 구현 예제
  • append(): 삽입
  • popleft(): 삭제
  • reverse(): 역순으로 바꾸기

---

2. 재귀 함수

(1) 재귀 함수(Recursive Function)

• 자기 자신을 다시 호출하는 함수
• 메모리 제한으로 재귀의 깊이 제한이 있음
• 무한 호출을 방지하기 위해 종료 조건을 반드시 명시할 것

종료 조건을 명시한 재귀 함수 예시

• 유의사항
  • 모든 재귀 함수는 반복문으로 동일한 기능 구현 가능
  • 반복문보다 유리한 경우도 있고 불리한 경우도 있음
  • 컴퓨터가 함수 연속 호출 시 메모리 내부의 스택 프레임에 쌓임
    • 스택을 사용해야할 때 스택 라이브러리 대신에 재귀 함수를 이용하는 경우多

(2) 예제

• 팩토리얼 구현

• 최대공약수 계산(유클리드 호제법) 예제
  • 2개의 자연수에 대한 최대공약수를 구하기
  • 유클리드 호제법: 두 자연수 A, B(A>B)에 대하여 A를 B로 나눈 나머지 R이 있을 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
  • 예시

---

3. DFS 알고리즘

(1) DFS(Depth-First Search)

• 깊이 우선 탐색
• 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(재귀 함수) 활용
  1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
  3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  4. 2-3번의 과정을 수행할 수 없을 때까지 반복

(2) 동작 예시

• 동작 기준 확인
• 가장 깊게 들어 갔다가 나와서 탐색

(3) 소스코드 예제

• 인덱스 0에 대한 내용은 비워둠
• 인접한 노드들을 모아서 정보 표현
• 방문 처리를 위한 1차원 리스트를 False로 초기화 + 인덱스 0을 고려하여 [크기+1]로 표현

---

4. BFS 알고리즘

(1) BFS(Breadth-First Search)

• 너비 우선 탐색
• 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 사용
• 동작 과정
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노트를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

(2) 동작 예시

(3) 소스코드

---

5. DFS & BFS 기초 문제 풀이

(1) 음료수 열려 먹기

문제 설명

문제 조건

- 문제 풀이

1. 강의 풀이

 

2. 내 풀이

- 해결 아이디어:

- 정당성 분석: 

(2) 미로 탈출

문제 설명

문제 조건

- 문제 풀이

1. 강의 풀이

 

2. 내 풀이

- 해결 아이디어:

- 정당성 분석: