Chapter 4-4. 그래프 순회 방법 2️⃣ - BFS(너비 우선 탐색)
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 4. 그래프
🚖 BFS
가까운 순서대로 방문한다.
- 출발 정점을 기준으로 가까운 순서대로 차례 차례 방문함.
- 예를 들어 순회을 0 정점에서 시작한다면
0정점에서 거리 1 (간선 1 개를 타야 갈 수 있는) 👉1,30정점에서 거리 2 (간선 2 개를 타야 갈 수 있는) 👉2,40정점에서 거리 3 (간선 3 개를 타야 갈 수 있는) 👉5- 최종적으로 BFS 순회는 0 1 3 2 4 5 순으로 방문하게 된다.
Queue큐로 구현한다.
- 그 때, 그 때 방문하는 정점마다 가장 가까운 거리의 정점들을 큐에 넣는다.
- 선입선출. 즉, 들어간지 오래된 정점부터 빠져나오게 된다.
- DFS 👉 다양한 용도에 사용 됨
- BFS 👉 거의 한 가지 용도로만 사용 된다! ⭐최단 거리 길 찾기⭐>
BFS 코드
using System;
using System.Collections.Generic;
namespace Excercise
{
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
public void BFS(int start)
{
bool[] found = new bool[6]; // false로 초기화 되어 있음
Queue<int> q = new Queue<int>();
q.Enqueue(start);
found[start] = true;
while (q.Count > 0)
{
// 1. 방문
int now = q.Dequeue();
Console.WriteLine(now);
// 2. 나와 가까운 정점들 중 방문하지 않은 애가 있다면 큐에 추가하여 예약
for (int next = 0; next < 6; next++)
{
if (adj[now, next] == 0) // 연결 되어 있지 않으면 스킵
continue;
if (found[next]) // 이미 방문한 애라면 스킵
continue;
// 예약
q.Enqueue(next);
found[next] = true;
}
}
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
graph.BFS(0); // 0 1 3 2 4 5
}
}
}
큐에 다음에 방문할 정점들을 추가한다. 즉, 다음에 방문할 정점들을 순서대로 예약하는 것.
- 아래 과정을 반복한다.
- 1️⃣ 방문 int now = q.Dequeue();
now예약 큐에서 들어간지 가장 오래된 정점을 꺼내온다.
- 2️⃣ 현재 방문하고 있는 정점
now가 앞으로 방문할 수 있는 정점들을 큐에 넣어 예약하기- 모든 정점들을 검사한다. (
next)now와 연결 되어 있는 곳이고 and 아직 방문하지 않는 정점이라면- 해당 정점
next를 다음에 방문할 수 있도록 큐에 넣어 예약한다. found로 한번이라도 예약된 적이 있다는 것을 체크하기
- 해당 정점
- 모든 정점들을 검사한다. (
- 1️⃣ 방문 int now = q.Dequeue();
- 출발지를 기점으로 거리 순서대로 가까운 정점들을 차례대로 방문하게 된다.
graph.BFS(0)👉 0 1 3 2 4 5 순으로 방문
BFS 순회한 노드들로부터 부모, 거리 정보 얻기
using System;
using System.Collections.Generic;
namespace Excercise
{
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
public void BFS(int start)
{
bool[] found = new bool[6]; // 한번이라도 예약된적이 있는지 여부
int[] parent = new int[6]; // 내 부모가 누구인지
int[] distance = new int[6]; // 내가 오기까지 얼마의 거리가 걸렸는지
Queue<int> q = new Queue<int>();
q.Enqueue(start);
found[start] = true;
parent[start] = start; // 출발지는 자기 자신이 부모라고 하자.
distance[start] = 0;
while (q.Count > 0)
{
// 1. 방문
int now = q.Dequeue();
Console.WriteLine(now);
// 2. 나와 가까운 정점들 중 방문하지 않은 애가 있다면 큐에 추가하여 예약
for (int next = 0; next < 6; next++)
{
if (adj[now, next] == 0) // 연결 되어 있지 않으면 스킵
continue;
if (found[next]) // 이미 한번이라도 예약된적이 있는 애라면 스킵
continue;
// 예약
q.Enqueue(next);
found[next] = true;
parent[next] = now;
distance[next] = distance[now] + 1;
}
}
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
graph.BFS(0); // 0 1 3 2 4 5
}
}
}
found👉 한번이라도 예약된적이 있는지parent👉 해당 인덱스에 대응하는 정점의 부모가 누구인지distance👉 출발지로부터 해당 인덱스에 대응하는 정점까지의 거리
// 예약
q.Enqueue(next);
found[next] = true;
parent[next] = now;
distance[next] = distance[now] + 1;
- 방문할 수 있는 정점
next을 큐에 예약할 때parent,distance도 함게 업뎃next의 부모는now(now로부터 연결 정점을 찾은 것이므로)start로부터next까지의 거리는now까지의 거리인distance[now]에서 1 더한다.
parent👉 0 0 1 0 3 4- 0 정점 부모 - 0
- 1 정점 부모 - 0
- 2 정점 부모 - 1
- 3 정점 부모 - 0
- 4 정점 부모 - 3
- 5 정점 부모 - 4
distance👉 0 1 2 1 2 3- 거리 0 - 출발지인 정점 0
- 거리 1 - 정점 1, 정점 3
- 거리 2 - 정점 2, 정점 4
- 거리 3 - 정점 5
이처럼 BFS를 통해 해당 정점까지의 최단 거리를 정보를 담을 수 있다. 👉 최단 거리 길 찾기에 사용 됨.
🚖 BFS 를 사용한 미로 길 찾기
BFS 는 거의 한 가지 용도로만 사용 된다! ⭐최단 거리 길 찾기⭐>
미로의 타일 또한 그래프로 나타낼 수 있다. 타일 하나 하나를 정점(Vertex)으로 보고, 현재 타일로부터 해당 타일이 갈 수 있는 타일이라면 연결(Edge) 되는 것으로 표현할 수 있고, 갈 수 없는 벽이라면 연결이 되어 있지 않은 관계라고 생각해볼 수 있다.
📜Player.cs - BFS
public void Initialize(int posY, int posX, Board board)
{
PosX = posX;
PosY = posY;
_board = board;
BFS();
}
void BFS()
{
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
bool[,] found = new bool[_board.Size, _board.Size];
Pos[,] parent = new Pos[_board.Size, _board.Size];
Queue<Pos> q = new Queue<Pos>();
q.Enqueue(new Pos(PosY, PosX)); // 시작점
found[PosY, PosX] = true;
parent[PosY, PosX] = new Pos(PosY, PosX);
while(q.Count > 0)
{
Pos pos = q.Dequeue();
int nowY = pos.Y;
int nowX = pos.X;
for (int i = 0; i < 4; i++)
{
int nextY = nowY + deltaY[i];
int nextX = nowX + deltaX[i];
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
if (found[nextY, nextX])
continue;
q.Enqueue(new Pos(nextY, nextX));
found[nextY, nextX] = true;
parent[nextY, nextX] = new Pos(nowY, nowX);
}
}
int y = _board.DestY;
int x = _board.DestX;
while (parent[y, x].Y != y || parent[y, x].X != x)
{
_points.Add(new Pos(y, x));
Pos pos = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
오른 손 법칙에서 그랬던 것과 마찬가지로 *Update 함수에서 플레이어의 위치를 프레임마다 결정하지 않고 미리 플레이어 위치 초기화 과정에서 미리 도착지까지 향하는 길(플레이어 위치들)을 결정해두고 리스트에 저장해둔다. Update 함수에서는 리스트에 있는 타일들을 꺼내면 될 뿐.*
deltaY,deltaX- 반시계 방향으로 Up, Left, Down, Right 순으로
- Up 방향으로 가기 위해선 Y 방향으로
deltaY[0](-1) 만큼, X 방향으로deltaX[0](0) 만큼 이동하면 된다. - Left 방향으로 가기 위해선 Y 방향으로
deltaY[1](0) 만큼, X 방향으로deltaX[1](-1) 만큼 이동하면 된다. - Down 방향으로 가기 위해선 Y 방향으로
deltaY[2](1) 만큼, X 방향으로deltaX[2](0) 만큼 이동하면 된다. - Right 방향으로 가기 위해선 Y 방향으로
deltaY[3](0) 만큼, X 방향으로deltaX[3](1) 만큼 이동하면 된다.
- Up 방향으로 가기 위해선 Y 방향으로
- 반시계 방향으로 Up, Left, Down, Right 순으로
found👉 한번이라도 예약된적이 있는 타일 체크parent👉 해당 타일의 부모 (연결된 이전 노드)q👉 추후 방문할 정점들을 큐에 추가하여 예약. 자신의 가까운 정점들을 차례로 추가한다.- 시작하기
q큐에 시작 위치(인수로 들어온 PosX, PosY) 넣기found일단 시작 위치는 방문 처리 trueparent시작 위치의 부모는 자기 자신
- 큐가 빌 때까지, 즉 더 이상 예약 된 정점이 아무 것도 없을 때 까지 아래 과정을 반복한다.
- 1️⃣ 큐에서 꺼내기 (현재 방문 중) 👉
nowY,nowX - 2️⃣ 다음에 방문할 수 있도록 큐에 예약하기
- 현재 방문 중인
nowY,nowX을 기준으로 4 개의 방향 Up, Left, Dowwn, Right 검사 (nextY,nextX) 👉 본인 기준 가장 가까운 정점을 검사하는 것과 같다. 본인 주변 4 방향 타일을 검사하는 것이니까.- 런타임 에러 방지(인덱스 벗어나진 않는지 검사)
- 1️⃣
nextY,nextX가 갈 수 있는 곳인지 (벽인지) 검사- 그래프로 따지면 연결 되지 않은 곳인지를 검사
- 2️⃣
nextY,nextX가 방문 했던 곳인지 검사
- 검사 통과 되었으면 방문 가능한 정점이므로 큐에 추가하여 예약하자.
- 큐에
nextY,nextX추가 nextY,nextX미리 방문 체크nextY,nextX의 부모(연결된 이전 정점)는nowY,nowX
- 큐에
- 현재 방문 중인
- 1️⃣ 큐에서 꺼내기 (현재 방문 중) 👉
- 여기까지 완료 하면
parent에 벽이 아닌 모든 타일들에 자신의 이전 정점 정보가 들어간다.- 목적지를 시작으로 목적지부터 거꾸로 부모를 타고 타고 올라가며 그 길을 리스트에 저장하자. 시작점에 도달할 때까지 👉 최단 경로
- 그 때 그 때 정점을 받문할 때마다 자신과 가장 가까운, 즉 바로 4 방향중에 하나로 연결된 정점들을 우선적으로 순서대로 방문하기 때문에 ⭐어떤 정점이던 간에 부모를 타고 타고 올라가면 출발지까지 최단 경로로 올라갈 수 있다는게 보장된다.⭐
- BFS 언제나 가까운 거리 순으로 방문했으므로 예를 들어 지금 정점5를 방문 중이라면 출발지부터 정점5까지 갈 수 있는 길 중 최단 거리다.
- 그 때 그 때 정점을 받문할 때마다 자신과 가장 가까운, 즉 바로 4 방향중에 하나로 연결된 정점들을 우선적으로 순서대로 방문하기 때문에 ⭐어떤 정점이던 간에 부모를 타고 타고 올라가면 출발지까지 최단 경로로 올라갈 수 있다는게 보장된다.⭐
- 시작점은 부모가 자기 자신과 같으므로 부모와 자기 자신이 같을 때까지 반복하면 된다. 그게 바로 시작점에 도착한 것.
- 목적지를 시작으로 목적지부터 거꾸로 부모를 타고 타고 올라가며 그 길을 리스트에 저장하자. 시작점에 도달할 때까지 👉 최단 경로
- 마지막으로 리스트를 Reverse 뒤집어 주면 출발지 부터 목적지까지의 최단 경로 타일들이 저장된 리스트가 되는 것이다.
- 마지막으로 _points.Add(new Pos(y, x)); 한번 더 추가해준 이유는 출발지 정점은 while 조건문에 위배되서 while문을 못 돌아서 리스트에 추가가 안되기 때문.
- 리스트를 순서대로 쭉 돌며 플레이어 위치를 업뎃해나가면 그게 바로 최단 경로.
📜Player.cs - 전체 코드
namespace Algorithm
{
class Pos
{
public Pos(int y, int x) { Y = y; X = x; }
public int Y;
public int X;
}
class Player
{
public int PosY { get; private set; }
public int PosX { get; private set; }
Random _random = new Random();
Board _board;
enum Dir // 반시계방향
{
Up = 0,
Left = 1,
Down = 2,
Right = 3
}
int _dir = (int)Dir.Up;
List<Pos> _points = new List<Pos>();
public void Initialize(int posY, int posX, Board board)
{
PosX = posX;
PosY = posY;
_board = board;
BFS();
}
void BFS()
{
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
bool[,] found = new bool[_board.Size, _board.Size];
Pos[,] parent = new Pos[_board.Size, _board.Size];
Queue<Pos> q = new Queue<Pos>();
q.Enqueue(new Pos(PosY, PosX)); // 시작점
found[PosY, PosX] = true;
parent[PosY, PosX] = new Pos(PosY, PosX);
while(q.Count > 0)
{
Pos pos = q.Dequeue();
int nowY = pos.Y;
int nowX = pos.X;
for (int i = 0; i < 4; i++)
{
int nextY = nowY + deltaY[i];
int nextX = nowX + deltaX[i];
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
if (found[nextY, nextX])
continue;
q.Enqueue(new Pos(nextY, nextX));
found[nextY, nextX] = true;
parent[nextY, nextX] = new Pos(nowY, nowX);
}
}
int y = _board.DestY;
int x = _board.DestX;
while (parent[y, x].Y != y || parent[y, x].X != x)
{
_points.Add(new Pos(y, x));
Pos pos = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
void RightHand()
{
// 현재 바라보고 있는 방향을 기존으로 좌표 변화를 나타냄
int[] frontY = new int[] { -1, 0, 1, 0 };
int[] frontX = new int[] { 0, -1, 0, 1 };
int[] rightY = new int[] { 0, -1, 0, 1 };
int[] rightX = new int[] { 1, 0, -1, 0 };
_points.Add(new Pos(PosY, PosX));
// 목적지 도착하기 전에는 계속 실행
// 실시간으로 로직 돌리기 전에, 렌더링도 하기 전에, 미리 길을 찾아 보는 것이다.
// 현재 바라보는 방향이 어디냐에 따라 오른손 위치가 다름.(왼쪽을 보고 있는 상태라면 오른손은 절대 기준으로 위쪽일것)
while (PosY != _board.DestY || PosX != _board.DestX)
{
// 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인
if (_board.Tile[PosY + rightY[_dir], PosX + rightX[_dir]] == Board.TileType.Empty)
{
// 오른쪽으로 가기
// 1. 오른쪽 방향으로 90 도 회전
_dir = (_dir - 1 + 4) % 4;
// 2. 앞으로 한 보 전진
PosY = PosY + frontY[_dir];
PosX = PosX + frontX[_dir];
_points.Add(new Pos(PosY, PosX));
}
// 2. 현재 바라보는 방향을 기준으로 앞 쪽으로 갈 수 있는지
else if (_board.Tile[PosY + frontY[_dir], PosX + frontX[_dir]] == Board.TileType.Empty)
{
// 앞으로 한 보 전진
PosY = PosY + frontY[_dir];
PosX = PosX + frontX[_dir];
_points.Add(new Pos(PosY, PosX));
}
else
{
// 왼쪽 방향으로 90 도 회전 해주고 다음 반복 하러 (반시계방향으로 여러 방향 따져봄)
_dir = (_dir + 1 + 4) % 4;
}
}
}
const int MOVE_TICK = 10; // 10밀리세컨즈 = 0.01 초 마다 움직이게
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
return;
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK) // 이부분은 0.1초마다 실행
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
}
🚖 BFS 단점
BFS 는 모든 경로를 동일한 조건으로 이동할 수 있을 때만 사용이 가능하다. 가중치 있는 그래프에선 X
- 제한적인 상황에서만 사용이 가능
- 가중치가 없이 모든 정점이 동등한 경우에만 사용 가능
- 만약 상하좌우 뿐만이 아니라 대각선 이동도 가능하여 총 8 개의 방향으로 움직일 수 있다면 (즉, 연결되어 있는 정점이 8개라면)
- 상하좌우 이동 비용이 1 이라면
- 대각선 이동 비용은 \(sqrt(2)\) 이기 때문에 대각선과 상하좌우 정점들이 서로 동등하지 못하다.
- BFS는 자신과 연결되어 있는 정점들을 모두 차례대로 동등하게 탐색하는데, 가중치가 다르므로 거리에 있어 모호해지기 때문이다.
가중치 있는 그래프는 다익스트아 최단 경로 알고리즘 에서 순회
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기