[이코테2021] 3강. DFS/BFS

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

- 그래프 탐색 알고리즘 대표 1. DFS 2.BFS

- 코테에서 매우 자주 등장하는 유형이므로 DFS/BFS를 반드시 숙지해야함

 

- 스택 자료구조 : 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

- 입구와 출구가 동일한 형태 ex) 박스 쌓기 (약간 눕혀있는 뚜껑없는 물병 생각하면 된다.)

 

스택 구현 예제

 

- python에서는 append와 pop으로도 스택 구현을 가능하다. 따라서 다른 모듈 필요하지 않음

- append와 pop은 O(1) 시간복잡도 이다

 

- 큐 자료구조 : 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조

- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태 (물병의 뚜껑과 바닥이 모두 뚫려서 눕혀있는 상태)

 

큐 구현 예제

 

- 스택과 달리 큐는 deque 모듈 이용하자 (덱모듈)

기본적으로 모듈 사용없이 가능하지만 그러면 시간복잡도가 높아지므로 deque를 이용하는 것이 좋음

- append와 popleft를 사용한다. O(1) 시간복잡도이다.

- append는 list의 append와 같은 개념임

 

만약, list 특정 인덱스 위해 pop을 하면 꺼내서 저장하는 시간 복잡도 O(k)가 필요하므로 deque를 사용하자

 

---

 

- 재귀 함수(Recursive Function) : 자기 자신을 다시 호출하는 함수

- 그러나 python은 최대 재귀 깊이 초과 제한이 있으므로 오류 메세지가 발생

 

- 재귀는 실제로는 스택과 같은 방식으로 실행됨.

재귀함수 호출을 다 끝낸 후 끝낸 순서대로 종료함

 

- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함

 

팩토리얼 구현 예제

 

- 재귀함수를 효과적으로 사용할 수 있는 방법 중 또다른 하나는 유클리드 호제법이다

- 유클리드 호제법은 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘

1. 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R 이라고 하자

2. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다

- 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성 가능

 

유클리드 호제법 예시

 

- 재귀 함수와 반복문은 서로 구현 가능

- 특정 상황에 따라 필요한 방법 사용해야 함

- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임

- 그래서 스텍 사용 시 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우도 많다. ex) DFS

 

---

 

- DFS(Depth-First-Search) : 깊이 우선 탐색이며, 스택 자료 구조(혹은 재귀 함수)를 이용한다.

1. 탐색 시각 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리한다.

   방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼낸다.

3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

DFS 동작 예시 [step 0]

 

- DFS는 방문 기준을 보통 번호가 낮은 인접 노드부터 한다.

 

DFS 동작 예시 [step 1]

 

DFS 동작 예시 [step 2]

 

DFS 동작 예시 [step 3]

 

DFS 동작 예시 [step 4]

 

DFS 동작 예시 [step 5]

 

DFS 동작 예시 [step 6]

 

DFS 동작 예시 

 

- 이렇게 실제로 깊게 들어갔다 나오는 구조이기 때문에 스택보다 재귀 함수를 이용한다

 

DFS 소스코드 예제

 

<그래프 초기화 방법>

- 2차원 리스트로 만든다.

- 보통 그래프 문제는 1번 노드부터 시작하기 때문에 0번 인덱스는 비워두고 1번 인덱스를 1번 노드라고 간주하고 해당 노드에 인접한 노드가 무엇인지 초기화한다.

- 각 인덱스는 각 노드 번호가 인접한 번호를 적어놓은 것이다.

 

<방문 처리>

- 1차원 리스트이며, 기본 값은 false

- 1번~8번 노드까지 사용하기 때문에 0번 인덱스는 사용 안하므로 하나 더 큰 리스트를 만든다.

 

---

 

- BFS(Breadth-First Search) : 너비 우선 탐색이며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조 이용한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 하낟.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

3. 2번이 더이상 사용하지 않을 때까지 반복한다.

 

- 특히, BFS는 특정 조건에서 최단 거리를 묻는 문제에서도 자주 사용한다.

 

BFS 동작 예시 [step 0]

 

BFS 동작 예시 [step 1]

 

BFS 동작 예시 [step 2]

 

BFS 동작 예시 [step 3]

 

BFS 동작 예시 [step 4]

 

BFS 동작 예시 [step 5]

 

BFS 동작 예시

 

- 가까운 노드부터 방문한다는 점!!

- 간선이 동일한 조건에서 최단 거리 문제에서 사용되는 BFS

 

BFS 소스코드

 

<그래프 초기화 방법>

- 2차원 리스트로 만든다.

- 보통 그래프 문제는 1번 노드부터 시작하기 때문에 0번 인덱스는 비워두고 1번 인덱스를 1번 노드라고 간주하고 해당 노드에 인접한 노드가 무엇인지 초기화한다.

- 각 인덱스는 각 노드 번호가 인접한 번호를 적어놓은 것이다.

 

<방문 처리>

- 1차원 리스트이며, 기본 값은 false

- 1번~8번 노드까지 사용하기 때문에 0번 인덱스는 사용 안하므로 하나 더 큰 리스트를 만든다.

 

 

- deque을 이용해서 하려면 popleft와 append를 이용한다.

 

---

 

<문제> 음료수 얼려 먹기

 

<문제> 음료수 얼려 먹기 조건

 

<문제 해결 아이디어>

- 연결 요소가 몇 개인지 확인하기 위해 DFS와 BFS를 이용

- 서로 인접한 노드 형태로 보면 된다.

- 상하좌우로 연결된 것들은 노드로 연결 되어 있다고 보면 된다.

- 연결된 모든 노드의 방문 처리를 되고, 나머지 방문이 안되는 것은 false가 되겠죠

- DFS를 활용하는 알고리즘

1. 특정 지점의 상하좌우 살펴보ㅗㄴ후 주변 지점중에서 값이 '0'이면서 아직 방문하지 않은 지점 있다면 방문

2. 방문한 지점에서 다시 상하좌우 살펴보면서 방문을 진행하면서 과정을 반복하면, 연결된 모든 지점 방문 가능

3. 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트 한다.

 

<문제> 음료수 얼려 먹기

 

<문제> 미로 탈출

<문제> 미로 탈출 조건

 

<문제 해결 아이디어>

- BFS는 간선의 비용이 모두 같을 때 최단 거리를 탐색할 때 용이

- 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.

- 상하좌우로 연결된 모든 노드로의 거리가 1로 동일

 

<문제> 미로 찰출 [step1]

 

 

<문제> 미로 찰출 [step2]

 

<문제> 미로 찰출 [step3]

 

<문제> 미로 찰출 소스코드

- BFS는 큐 즉, deque를 이용함