BFS
- Breadth First Search, 너비 우선 탐색
- 가까운 노드부터 탐색하는 알고리즘
- DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하지만, BFS는 그 반대이다!
- BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다
- 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면, 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다
- BFS의 동작 방식은 아래와 같다
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다
- 이제 예시 그래프를 통해 동작 과정을 자세하게 살펴보자
- 그래프의 가정은 DFS에서의 예시와 동일하며, 큐에는 원소가 위로 들어오고 아래로 나간다고 가정한다!
STEP 1) 시작 노드인 1을 큐에 삽입하고 방문 처리를 한다. 방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 논드는 하늘색으로 표현한다.
STEP 2) 큐에서 노드 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8을 모두 큐에 삽입하고 방문 처리한다.
STEP 3) 큐에서 노드 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문 처리를 한다
STEP 4) 큐에서 노드 3을 꺼내고 방문하지 않은 인접 노드 4와 5를 모두 큐에 삽입하고 방문 처리를 한다.
STEP 5) 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.
STEP 6) 큐에서 노드 7을 꺼내고 방문하지 않은 인접 노드 6을 큐에 삽입하고 방문 처리를 한다.
STEP 7) 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.
결과적으로 노드의 탐색 순서(큐에 들어간 순서)는 다음과 같다!
1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6
잘 보면 시작 노드인 1번 노드에서 가까운 순서대로 방문하고 있다!
거리가 1인 노드 2, 3, 8을 방문하고, 거리가 2인 노드 7, 4, 5를 방문하고 마지막으로 거리가 3인 6을 방문한다
- 너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다
- 실제로 구현함에 있어 파이썬에서는 deque 라이브러리를 사용하는 것이 좋으며, C++에서는 queue 자료형을 사용하면 된다
- 탐색을 수행함에 있어 O(N)의 시간이 소요된다
- 일반적으로 수행 시간은 DFS보다 BFS가 좋은 편이다~
- 이제 실제로 코드로 구현해보면서 완벽하게 이해를 해보자!
파이썬 코드)
from collections import deque
#BFS 메서드 정의
def bfs(graph, start, visited):
#큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
#현재 노드를 방문 처리
visited[start] = True
#큐에 아무것도 없을 때까지 반복
while queue:
#큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
#각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)deque에서는 popleft를 통해 먼저 들어온 원소를 먼저 뺄 수 있다!
C++ 코드)
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
bool visited[9];
vector<int> graph[3];
//BFS 함수 정의
void bfs(int start)
{
queue<int> q;
q.push(start);
//현재 노드를 방문 처리
visited[start]=true;
//큐에 아무것도 없을 때까지 반복
while(!q.empty())
{
//큐에서 원소를 하나 뽑아 출력
int x = q.front();
q.pop();
cout<<x<<' ';
//해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i=0;i<graph[x].size();i++)
{
int y = graph[x][i];
if(!visited[y])
{
q.push(y);
visited[y]=true;
}
}
}
}
int main()
{
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
return 0;
}c++에서는 #include <queue> 헤더파일을 통해 queue<int> q를 선언하여 사용한다
그 외의 알고리즘은 BFS 설명과 동일하게 구현된다!
자바 코드)
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// BFS 함수 정의
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
System.out.print(x + " ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
bfs(1);
}
}지금까지 DFS와 BFS의 구현에 대해 알아보았고, 이제 간단히 정리하여 보자!
| DFS | BFS | |
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
- 앞서 DFS와 BFS를 설명하는데 전형적인 그래프 그림을 이용했지만, 1차원 배열이나 2차원 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다
- 특히 DFS와 BFS 문제 유형이 그러하다!
예를 들어 게임 맵이 3X3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자
게임 캐릭터가 (1,1) 좌표에 있다고 표현할 때처럼 말이다!
이 때 각 좌표를 상하좌우로만 이동할 수 있다면 어떨까?
모든 좌표의 형태를 다음처럼 그래프의 형태로 바꿔서 생각할 수 있다
이런식으로 코테에서 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하면 풀이를 조금 더 쉽게 떠올릴 수 있다!
그러므로 코테에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민하도록 하자!
다음으로는 실전 문제를 풀어보자!
'코딩테스트 > 이코테' 카테고리의 다른 글
| [CH5 DFS/BFS] 미로 탈출 (0) | 2021.12.27 |
|---|---|
| [CH5 DFS/BFS] 음료수 얼려 먹기 (0) | 2021.12.25 |
| [CH5 DFS/BFS] 탐색 알고리즘 DFS/BFS (2) (0) | 2021.12.21 |
| [CH5 DFS/BFS] 탐색 알고리즘 DFS/BFS (1) (0) | 2021.12.21 |
| [CH5 DFS/BFS] 꼭 필요한 자료구조 기초 (0) | 2021.12.20 |
댓글