9주차
그래프나 격자에서 탐색을 할 때, 시작 지점에서 가까운 곳부터 차례대로 탐색하는 알고리즘
- Breadth-First Search의 약자로, 한국어로는 너비 우선 탐색이라고도 부른다.
- 현재 위치에서 갈 수 있는 곳들을 먼저 모두 확인 후에 그 다음 단계로 이동한다고 생각하면 된다.
- BFS는 시작점에서부터 거리가 가까운 순서대로 탐색한다
거리 0: 시작점
거리 1: 시작점과 바로 연결된 지점
거리 2: 거리 1 지점들과 연결된 지점
거리 3: 거리 2 지점들과 연결된 지점
예를 들어 다음과 같은 그래프가 있다면,
1
/ \
2 3
/ \ \
4 5 6
1번 노드에서 BFS를 수행하면 탐색 순서는 다음과 같다.
1 → 2 → 3 → 4 → 5 → 6
이처럼 BFS는 가까운 노드부터 차례대로 탐색하기 때문에, 최단거리 문제에서 자주 사용된다.
- BFS는 먼저 발견한 위치를 먼저 탐색해야 하기 때문에,
Queue자료구조를 사용한다. -
Queue는 먼저 들어온 데이터가 먼저 나가는 구조이다.- BFS는 이러한
Queue의 특징을 이용해 가까운 위치부터 순서대로 탐색한다.
- BFS는 이러한
BFS의 기본 흐름은 다음과 같다.
- 시작점을 Queue에 넣는다.
- 시작점을 방문 처리한다.
- Queue가 빌 때까지 반복한다.
- Queue에서 현재 위치를 꺼낸다.
- 현재 위치와 연결된 다음 위치들을 확인한다.
- 아직 방문하지 않은 위치라면 방문 처리 후 Queue에 넣는다.
- BFS에서는 이미 방문한 위치를 다시 방문하지 않기 위해
visited배열을 사용한다. - 방문 처리를 하지 않을 경우, 같은 노드를 반복해서 탐색하는 경우가 생길 수 있다.
- ex.
A ↔ B로 연결되어 있을 때, 방문 처리가 없다면A 방문 → B 방문 → A 방문 → B 방문 ...같은 무한 반복이 발생할 수 있다.
- ex.
- 이를 방지하기 위해 BFS에서는 아직 방문하지 않은 곳이라면 방문 처리 후에
Queue에 넣는다.
DFS와 BFS는 모두 그래프나 격자를 탐색할 때 사용하는 알고리즘이지만, 탐색하는 순서에 차이가 있다.
| 구분 | DFS | BFS |
|---|---|---|
| 의미 | 깊이 우선 탐색 | 너비 우선 탐색 |
| 탐색 방식 | 한 방향으로 끝까지 탐색 | 가까운 곳부터 차례대로 탐색 |
| 사용 자료구조 | Stack 또는 재귀 | Queue |
| 특징 | 가능한 경로를 끝까지 파고듦 | 같은 거리의 노드를 먼저 탐색 |
| 자주 사용되는 문제 | 모든 경우 탐색, 백트래킹, 연결 요소 탐색 | 최단거리, 최소 이동 횟수, 확산 문제 |
- DFS는 한 길을 끝까지 들어간 뒤 더 이상 갈 수 없으면 되돌아오는 방식
- BFS는 시작점에서 가까운 곳을 먼저 모두 확인한 뒤 다음 거리의 노드로 이동하는 방식
따라서 최단거리나 최소 이동 횟수를 구해야 하는 문제에서는 BFS가 자주 사용된다.
- BFS는 시작점에서 가까운 위치부터 차례대로 탐색한다.
- 즉, 거리 1인 위치를 모두 탐색한 뒤 거리 2인 위치를 탐색하고 그 다음 거리 3인 위치를 탐색하는 방식으로 진행된다.
- 도착 지점에 처음 도달했을 때의 거리가 곧 최단 거리가 된다는 뜻!
- 단, BFS로 최단 거리를 구할 수 있는 경우는 보통 모든 이동 비용이 동일한 경우이다.
BFS는 문제 형태에 따라 크게 그래프 BFS와 격자 BFS로 나뉜다.
노드와 간선으로 이루어진 구조에서 연결된 노드를 탐색하는 방식
- 위 그래프에서 1번 노드부터 BFS를 수행하면 다음과 같은 순서로 탐색한다.
1 → 2 → 3 → 4 → 5 → 6
- 그래프 BFS에서는 각 노드가 어떤 노드와 연결되어 있는지를 저장하기 위해 보통 인접 리스트를 사용한다.
const graph = [
[], // 0번 노드는 사용하지 않는다고 가정
[2, 3], // 1번 노드와 연결된 노드
[1, 4, 5], // 2번 노드와 연결된 노드
[1, 6], // 3번 노드와 연결된 노드
[2], // 4번 노드와 연결된 노드
[2], // 5번 노드와 연결된 노드
[3] // 6번 노드와 연결된 노드
];function bfs(start, graph) {
const visited = Array(graph.length).fill(false);
const queue = [];
let head = 0;
// 시작 노드를 Queue에 넣고 방문 처리
queue.push(start);
visited[start] = true;
while (head < queue.length) {
// Queue에서 현재 노드 꺼내기
const current = queue[head++];
console.log(current);
// 현재 노드와 연결된 다음 노드 확인
for (const next of graph[current]) {
// 아직 방문하지 않은 노드라면
if (!visited[next]) {
visited[next] = true;
queue.push(next);
}
}
}
}- visited 배열을 만들어 각 노드의 방문 여부를 저장한다.
- queue에 시작 노드를 넣는다.
- 시작 노드를 방문 처리한다.
- Queue가 빌 때까지 반복한다.
- Queue에서 현재 노드를 꺼낸다.
- 현재 노드와 연결된 노드들을 확인한다.
- 아직 방문하지 않은 노드라면 방문 처리 후 Queue에 넣는다.
즉, 그래프 BFS의 핵심은
현재 노드와 연결된 노드들을 확인하면서, 아직 방문하지 않은 노드를 Queue에 넣는 것이다.
2차원 배열에서 상하좌우로 이동하며 탐색하는 방식
- 미로 탐색, 게임 맵 최단거리, 무인도 탐색, 토마토 익기 같은 문제에서 자주 사용된다.
예를 들어 다음과 같은 격자가 있다고 가정해 보자.
- 여기서
1은 이동할 수 있는 칸이고,0은 이동할 수 없는 칸이다.
- 위 격자에서
(0, 0)부터 BFS를 수행하면 다음과 같은 순서로 탐색한다.
(0,0) → (0,1) → (1,1) → (2,1) → (1,2) → (2,2)
- 격자 BFS에서는 현재 위치에서 상하좌우 네 방향을 확인해야 한다.
위 : (-1, 0)
아래 : (1, 0)
왼쪽 : (0, -1)
오른쪽 : (0, 1)
- 이를 보통 코드에서는
dx,dy배열로 아래와 같이 표현한다.
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];- 현재 위치가 (x, y)라면 다음 위치는 다음과 같이 계산한다.
const nx = x + dx[i];
const ny = y + dy[i];function bfs(startX, startY, maps) {
const n = maps.length;
const m = maps[0].length;
const visited = Array.from({ length: n }, () => Array(m).fill(false));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const queue = [];
let head = 0;
// 시작 위치를 Queue에 넣고 방문 처리
queue.push([startX, startY]);
visited[startX][startY] = true;
while (head < queue.length) {
const [x, y] = queue[head++];
console.log(x, y);
// 상하좌우 4방향 확인
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
// 격자 범위를 벗어나면 무시
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
// 이미 방문한 칸이면 무시
if (visited[nx][ny]) {
continue;
}
// 이동할 수 없는 칸이면 무시
if (maps[nx][ny] === 0) {
continue;
}
// 이동 가능한 칸이면 방문 처리 후 Queue에 넣기
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}- visited 2차원 배열을 만들어 각 칸의 방문 여부를 저장한다.
- 상하좌우 이동을 위해 dx, dy 배열을 만든다.
- 시작 위치를 Queue에 넣는다.
- 시작 위치를 방문 처리한다.
- Queue가 빌 때까지 반복한다.
- Queue에서 현재 위치를 꺼낸다.
- 현재 위치에서 상하좌우 네 방향을 확인한다.
- 격자 범위를 벗어난 위치는 무시한다.
- 이미 방문한 칸은 무시한다.
- 이동할 수 없는 칸도 무시한다.
- 이동 가능한 칸이라면 방문 처리 후 Queue에 넣는다.
즉, 격 BFS의 핵심은
현재 위치에서 상하좌우를 확인하면서, 범위 안에 있고 & 방문하지 않았고 & 이동 가능한 칸만 Queue에 넣는 것이다.
BFS는 다음과 같은 유형의 문제에서 자주 사용된다.
- 시작점에서 도착점까지 가장 짧은 거리를 구하는 문제
- 특정 위치까지 도달하기 위한 최소 이동 횟수를 구하는 문제
- 상하좌우로 이동하며 도착점까지 이동하는 문제
- 격자에서 연결된 영역의 개수나 크기를 구하는 문제