그냥 게임개발자
너비 우선 탐색(BFS, Breadth First Search) 본문
너비우선탐색이란
그래프를 탐색하는 알고리즘
어떠한 정점에서 시작해 다음 깊이의 정점으로 이동하기 전에 현재 깊이의 모든 정점을 탐색하여 방문한 정점은 다시 방문하지 않는 알고리즘
같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 자주 쓰입니다.
여기서 가중치는 무엇일까요?
지금 여기서 보면 0에서 1을 가는데 가중치는 10이 듭니다.
1에서 5를가는데 가중치는 5입니다.
즉 이 가중치가 같아야만!
너비우선 탐색 알고리즘을 사용할 수 있습니다.
그래서 BFS로 탐색을 한다는 것은 레벨별로 탐색한다는 뜻입니다.
이렇게 1레벨 2레벨 순
1. 빨강의 레벨에 속하는 노드 검사
2. 주황의 레벨에 속하는 노드 검사
3. 노랑의 레벨에 속하는 노드 검사
4. 초록의 레벨에 속하는 노드 검사
이런식으로 검사하는 방식이 BFS입니다.
그렇다면 이 알고리즘을 어떻게 구현을 해야할까요?
DFS는 배열 또는 vector를 통해 구현하였죠?
BFS는 Queue를 통해서 구현합니다.
위의 그림을 보면서 설명하겠습니다.
먼저 루트노드를 먼저 push를 합니다.
그러면 1이 들어오게 됩니다.
1이들어왔을 때는 방문이 되었으니 1은 이제 배제하고 자식을 넣어준 뒤 pop을 해줍니다.
1의 자식들은 2, 3, 4가 있으니 2, 3, 4를 push 해줍니다.
push 해줌과 동시에 2, 3, 4는 방문을 했으니 방문체크를 해줍니다.
이제 다시 queue에 담견진 정점들을 순서대로 검사를 해준 뒤 맨 첫번째의 정점을 꺼내 자식노드들을 체크해줍니다.
5라는 자식노드가 있으니 2를 pop해주고 5를 push 해줍니다.
이제 다시 3을 체크해서 3의 자식노드들을 추가하고 3은 방문체크해준 뒤 pop해줍니다.
같은 레벨먼저 검사한 뒤에 그 다음 레벨의 노드들을 순차적으로 검사하는 방식이 이렇습니다.
이해가 쉬웠나요?
그러면 수도코드를 한 번 봅시다.
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)오우 뭔가 좀 많네요 하나하나 해석해보죠.
BFS(G, u)
이 G와 u는 뭘까요?
G = Graph
u = 보통 정점을 설명하는데 여기서 from즉, 여기서부터!라는 소리
u.visited = 1이거는 말 그대로 from을 방문했다라고 체크한 것입니다.
q.push(u);queue에다가 u를 push하네요.
while (q.size())queue의 사이즈만큼 순회합니다.
u = q.front()
q.pop()시작점은 queue의 제일 위의것부터 시작하고
queue를 pop해줍니다.
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = u.visited + 1
q.push(v)이제 여기서 graph의 정점과 연관된 정점들을 검사해 방문했는지 체크하고 방문을 안했으면, 간선의 가중치를 넣어준 뒤 push 해줍니다.
이해가셨을까요?
좋아요
그렇다면 이것을 코드로 써보죠.
int N;
queue<int> q;
int visited[N];
vector<int> adj[N];
void BFS(int here)
{
q.push(here);
visited[here] = 1;
while(q.size())
{
int here = q.front();
q.pop();
for (int there : adj[here])
{
if (visited[there])
continue;
// 현재의 노드의 자식을 검사중이니
// 현재 노드의 거리 + 1이 해주니
// 현재 노드에서 자식까지의 거리는 2라는 값을 넣어주게 되는 것입니다.
visited[there] = vistied[here] + 1;
q.push(there);
}
}
}
수도코드랑 별 다를 게 없죠?
그렇다면 진짜 활용해보도록하죠.
위와 같은 그래프가 있을 때
BFS를 써서 탐색하는 코드를 써봅시다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[100];
int visited[100];
int nodeList[] = { 10, 12, 14, 16, 18, 20, 22, 24 };
void BFS(int here)
{
queue<int> q;
// 현재의 거리
visited[here] = 1;
q.push(here);
while (q.size())
{
int here = q.front();
q.pop();
for (int there : adj[here])
{
if (visited[there] == 0)
{
// 거리 넣어주기
visited[there] = visited[here] + 1;
q.push(there);
}
}
}
return;
}
int main()
{
adj[10].push_back(12);
adj[10].push_back(14);
adj[10].push_back(16);
adj[12].push_back(18);
adj[12].push_back(20);
adj[20].push_back(22);
adj[20].push_back(24);
BFS(10);
for (int i : nodeList)
{
cout << i << " : " << visited[i] << '\n';
}
cout << "10에서 24번까지 최단거리 : " << visited[24] - 1 << '\n';
}
음 다시 한 번 꼭 혼자서 나중에 작성해보도록해요,.
물론 저도요.
하하
마지막에 최단거리를 구할 때 visited[24] - 1하는 부분은 왜 그럴까요?
// 거리 넣어주기
visited[there] = visited[here] + 1;
q.push(there);이 로직 때문에 그렇습니다.
현재 처음 방문한 거리는 1로 우리가 체크를 해주었죠.
왜냐하면 방문하지 않은 거리를 0으로 체크하니까 그렇습니다.
visited[here] = 1;
그래서 우리는 자식 노드를 탐색해서 방문하지 않은 자리에 + 1을 해주어 거리를 넣어줬습니다.
그러면 처음 방문한 거리가 1이 되어 사실은 0부터 시작이라 -1을 해주는 겁니다.
visited[24] - 1그러면 10에서 24까지의 거리는 총 3이라는 값이 나옵니다.
결과값을 한 번 볼까요?
3이 나왔습니다.
아 저 진짜 실제로 작성했습니다.
근데 지금 이 코드에서는 가중치가 1입니다.
10 에서 12까지 가는데 +1을 해주었으니 말이죠.
근데 만약에 가중치가 2나 4였으면 어떨까요?
뭐 간단합니다.
만약 가중치가 2라면 실제 +1을 건드리기 보다.
ㅇㅇㅇ.....
근데 만약에 루트노드가 다수라면 어떨까요?
시작지점이 9, 10, 11이라고 하면 어떨까요?
void BFS(int here)
{
queue<int> q;
for (int i = 9; i < 12; ++i)
{
visited[i] = 1;
q.push(i);
}
}
이런식으로 작성하면 됩니다.
만약 가중치가 서로 다른 애들이라면 어떨까요?
예를 들어
이렇게 가중치가 서로 다르다라고 하면 어떨까요?
BFS를 사용하지 못합니다.
뭐 응용을 할 수는 있지만
BFS의 정의는 이런 방식이기 때문에 쓰지 못합니다.
가중치가 다른 간선이라면 다익스트라 알고리즘이나 벨만포드 알고리즘을 써야 합니다.
이거는 나중에 차차 포스팅하도록 하겠습니다.
그럼 BFS의 수도코드 아까 봤었죠?
BFS의 수도코드는 총 2개입니다.
방문처리만 하여 사용하는 방법
BFS(G, u)
u.visited = true
q.push(u)
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = true
q.push(v)
최단거리 배열을 방문하여 사용하는 방법
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)
좋아요
그렇다면 문제를 한 번 풀어보죠.
어떠한 N * M이 주어지고 캐릭터는 육지로만 갈 수 있다.
어떠한 도착지점의 좌표가 주어졌을 때 이 도착지점까지의 최단거리를 구하여야 한다.
갈 수 있는 곳은 1이며 갈 수 없는 곳은 0이다.
캐릭터는 상하좌우로만 움직일 수 있다.
첫번째 줄의 입력란은 맵의 크기
두번째 줄의 입력란은 캐릭터의 시작점
세번째 줄의 입력란은 맵의 지역
0 < N, M <= 100
예시 입력
5 5 // 맵의 크기
0 0 // 시작 지점
4 4 // 도착 지점
1 0 1 0 1
1 1 1 0 1
0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
한 번 풀어보시고 너무 어렵다 싶으면 아래 코드로 도움을 받아보세요.
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int arr[104][104];
int Y, X;
int goalY, goalX;
int visited[104][104];
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
void BFS(int _y, int _x)
{
queue<pair<int, int>> q;
visited[_y][_x] = 1;
q.push({ _y, _x });
// 방문한 거에서 상하좌우를 검색
while (q.size())
{
pair<int, int> here = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int ny = here.first + dy[i];
int nx = here.second + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M || arr[ny][nx] == 0)
continue;
// 방문 안했고 갈 수 있으면?
if (visited[ny][nx] == 0 && arr[ny][nx] == 1)
{
visited[ny][nx] = visited[here.first][here.second] + 1;
q.push({ ny, nx });
}
}
}
return;
}
int main()
{
cin >> N >> M;
cin >> Y >> X;
cin >> goalY >> goalX;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cin >> arr[i][j];
}
}
BFS(Y, X);
//for (int i = 0; i < N; ++i)
//{
// for (int j = 0; j < M; ++j)
// {
// cout << visited[i][j] << ' ';
// }
//}
cout << visited[goalY][goalX] << '\n';
}
아 이거 제가 직접 풀어본거에요!
아 이제 자야겠네요 너무 늦었어요..
끄으으으으읕
'내 개인적인 공부 > 알고리즘' 카테고리의 다른 글
| 깊이 우선 탐색(DFS, Depth First Search) (0) | 2024.04.23 |
|---|---|
| 연결된 컴포넌트(Connected Component) (1) | 2024.04.22 |
| 맵과 방향 벡터 (0) | 2024.04.22 |
| 인접행렬과 인접리스트의 차이 (0) | 2024.04.22 |
| 인접리스트 (0) | 2024.04.22 |
