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와 격자 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, 거리 2, 거리 3처럼 가까운 칸부터 탐색한다는 점이다.
- 격자 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는 다음과 같은 유형의 문제에서 자주 사용된다.
- 시작점에서 도착점까지 가장 짧은 거리를 구하는 문제
- 특정 위치까지 도달하기 위한 최소 이동 횟수를 구하는 문제
- 상하좌우로 이동하며 도착점까지 이동하는 문제
- 격자에서 연결된 영역의 개수나 크기를 구하는 문제
상하좌우로 이동할 수 있는 격자에서 최단거리를 구하는 문제
- BFS / 격자 탐색 / 최단거리
- 이 문제는 한 칸 이동할 때마다 비용이 항상 1로 동일하다.
- 따라서 시작점에서 가까운 칸부터 차례대로 탐색하는 BFS를 사용하면, 도착 지점에 처음 도달했을 때의 거리가 곧 최단거리가 된다.
import java.util.*;
class Solution {
public int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
boolean[][] visited = new boolean[n][m];
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> queue = new LinkedList<>();
// 시작 위치: (0, 0), 거리: 1
queue.offer(new int[]{0, 0, 1});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
// 도착 지점에 도달한 경우
if (x == n - 1 && y == m - 1) {
return distance;
}
// 상하좌우 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int 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;
}
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny, distance + 1});
}
}
// 도착할 수 없는 경우
return -1;
}
}from collections import deque
def solution(maps):
n = len(maps)
m = len(maps[0])
visited = [[False] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
# 시작 위치: (0, 0), 거리: 1
queue.append((0, 0, 1))
visited[0][0] = True
while queue:
x, y, distance = queue.popleft()
# 도착 지점에 도달한 경우
if x == n - 1 and y == m - 1:
return distance
# 상하좌우 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 맵 범위를 벗어난 경우
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# 이미 방문한 경우
if visited[nx][ny]:
continue
# 벽인 경우
if maps[nx][ny] == 0:
continue
visited[nx][ny] = True
queue.append((nx, ny, distance + 1))
# 도착할 수 없는 경우
return -1function solution(maps) {
const n = maps.length;
const m = maps[0].length;
// 각 칸의 방문 여부를 저장하는 2차원 배열
const visited = Array.from({ length: n }, () => Array(m).fill(false));
// 상, 하, 좌, 우 이동 방향
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
// Queue 역할을 할 배열
const queue = [];
let head = 0;
// 시작 위치는 (0, 0), 시작 칸도 지나간 칸에 포함되므로 거리는 1
queue.push([0, 0, 1]);
visited[0][0] = true;
// Queue가 빌 때까지 반복
while (head < queue.length) {
// Queue에서 현재 위치 꺼내기
const [x, y, distance] = queue[head++];
// 현재 위치가 도착 지점이라면 최단거리 반환
if (x === n - 1 && y === m - 1) {
return distance;
}
// 현재 위치에서 상하좌우 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, distance + 1]);
}
}
// BFS가 끝날 때까지 도착하지 못했다면 도달 불가능
return -1;
}- 맵의 행 개수
n과 열 개수m을 구한다. - 각 칸의 방문 여부를 저장할
visited2차원 배열을 만든다. - 상하좌우 이동을 위해
dx,dy배열을 만든다. - 시작 위치
(0, 0)을 Queue에 넣고 방문 처리한다. - 시작 칸도 지나간 칸에 포함되므로 거리는
1부터 시작한다. - Queue가 빌 때까지 BFS를 수행한다.
- Queue에서 현재 위치와 현재까지의 거리를 꺼낸다.
- 현재 위치가 도착 지점이면 현재 거리 값을 return 한다.
- 현재 위치에서 상하좌우 네 방향을 확인한다.
- 맵 범위를 벗어나거나, 이미 방문했거나, 벽인 칸은 무시한다.
- 이동 가능한 칸은 방문 처리 후 Queue에 넣는다.
- BFS가 끝날 때까지 도착하지 못하면
-1을 return 한다.
- 방문 처리는 보통 Queue에 넣는 순간 하는 것이 좋다.
-
Queue에서 꺼낼 때 방문 처리하면, 같은 위치가Queue에 여러 번 들어갈 수 있다.
// 추천
visited[nx][ny] = true;
queue.push([nx, ny]);-
nx,ny가 배열 범위를 벗어나면 런타임 에러가 발생할 수 있다.
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}- 격자에서는 보통
x를 행,y를 열로 생각한다.
maps[x][y]
visited[x][y]