BFS 너비 우선 탐색
개요
BFS 너비우선탐색
BFS는 그래프를 탐색하는 알고리즘으로 노드에서 시작해 이웃한 노드들을 우선적으로 탐색하는 알고리즘 이다.
같은 가중치를 가진 그래프에서 최단거리를 구할 때 사용되는 알고리즘이다.
시간 복잡도는 앞의 포스팅에서 소개한 DFS와 같으며 주어진 맵 전체를 탐색하며 한번 방문한 노드는 다시 방문하지 않기에 인접 리스트로 이뤄진 맵인 경우
O(V + E)
인접 행렬로 이뤄진 경우
O(V^2)
만약 가중치가 다른 그래프 내의 최단거리를 구해야 할 경우는 다익스트라, 벨만포드 알고리즘을 사용해야 한다.
너비 우선 탐색 (BFS)
특정 노드에서 가장 먼 곳의 노드부터 순차적으로 탐색한다.
수도코드
아래는 BFS의 수도코드다.
1
2
3
4
5
6
7
8
9
10
BFS(G, u)
u.visited = 1
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = u.visited + 1
q.push(v)
[출처] [알고리즘 강의] 2주차. 그래프이론, DFS, BFS, 트리순회 작성자 큰돌
특징
이전에 방문하지 않았더라면 가중치를 적용시켜 방문좌표에 가중치를 더한다.
BFS함수를 반복으로 호출하는 방법을 쓰며, 만약 이전에 방문을 했더라면 함수를 종료 시킨다.
예시문제 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
SOL
joy를 이용해 가야할 위치에 방문한 위치값 + 1 의 가중치를 이용하여 해결한다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <queue>
using namespace std;
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
// map
bool map[101][101];
int visited [101][101];
// map 크기
int n, m;
// 현 위치
int x, y;
int main()
{
cin >> n >> m;
for(int i=0; i < n; i++)
{
string str;
cin >> str;
// map 생성
for(int j=0; j < m; j++)
{
if(str[j] == '1')
map[i][j] = 1;
}
}
// (1, 1)에서 출발 함으로 해당 좌표 방문처리
visited[0][0] = 1;
queue<pair<int, int>> q;
// 방문한 곳 푸쉬
q.push({0, 0});
while(q.size())
{
// 현재 위치 값 초기화
y = q.front().first;
x = q.front().second;
q.pop();
// joy 탐색
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
// 범위 값을 넘어갈 경우, 이미 방문한 경우, 벽인 경우
if(ny < 0 || nx < 0 || ny >= n || nx >= m || !map[ny][nx])
continue;
if(visited[ny][nx])
continue;
// 위 조건이 아닐 경우 가산 값 추가
visited[ny][nx] += visited[y][x] + 1;
// 방문한 다음 위치 다시 푸쉬
q.push({ny, nx});
}
}
// 최단 거리 맵 출력
// for(int i=0; i < n; i++)
// {
// for(int j=0; j < m; j++)
// {
// cout << visited[i][j] << " ";
// }
// cout << endl;
// }
cout << visited[n-1][m-1] << endl;
return 0;
}