03. DFS/BFS

Background

BFS와 DFS 알고리즘을 이해하고 구현하기 위해서 기본적인 자료구조를 복습하고 넘어가자.

먼저, 스택과 큐 개념이다.

1. 스택이란?
   First in Last Out (선입후출) 구조로 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 차곡 차곡 위로 쌓게 되는데, 먼저 넣었던 것을 빼기 위해서는 위에 쌓은 박스들을 우선 제거해줘야한다. 스택 자료구조는 위와 같은 방식으로 동작한다. 이를 파이썬에서 구현하기위해서는 별도의 라이브러리는 필요하지 않고, 리스트를 활용하면된다. 리스트에서 append를 쓰면 박스를 쌓는거고 pop을 하면 가장 위에 있는 박스를 내려놓는거라고 이해하면 쉽다. 
2. 큐란?
   First in First Out (선입선출) 구조로 줄 서기에 비유할 수 있다. 놀이공원에 줄을 서면 먼저 선 사람이 놀이기구를 탄다고 생각하면 이해하기 쉽다. 큐 자료구조는 파이썬에서 구현하기위해서 collections 모듈에서 제공하는 deque를 활용하면된다. append는 줄을 선 거고 popleft를 하면 가장 먼저 줄을 선 사람이 놀이기구를 탄다고 이해하면 된다.

DFS란? 

Depth-First Search로 깊이 우선 탐색이라고 부른다. 쉽게 말해서 그래프를 탐색할 때, 최대한 깊숙이 들어가서 노드를 방문하고 다시 돌아가 다른 경로로 탐색을 하는 것을 의미한다.

DFS는 구현 시 스택 자료구조를 이용하며 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.

BFS란? 

Breadth-First Search로 너비 우선 탐색이라고 부른다. 쉽게 말해서 그래프를 탐색할 때, 가까운 노드부터 먼저 탐색하는 알고리즘이다.

BFS는 구현 시 큐 자료구조를 이용하며 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

이 개념을 복습할 수 있는 가장 좋은 문제는 `백준 1260번`이다! 아래 문제 풀이 링크를 참고 바란다. 

---

DFS/BFS 문제 풀이 링크 모음 

• [이코테/DFS와BFS] 음료수 얼려 먹기
• [이코테/DFS와BFS] 미로 탈출
• [백준/1260번] DFS와 BFS
• [백준/2606번] 바이러스
• [백준/11725번] 트리의 부모찾기 
• [백준/1325번] 효율적인 해킹
• [백준/14940번] 쉬운 최단거리
• [백준/2667번] 단지번호 붙이기