(C#) 47. BFS 최단 경로 알고리즘
Maze with BFS
(C#) 47. BFS 최단 경로 알고리즘
BFS ()
- 최초 작성일: 2023년 1월 13일(금)
##
BFS에 대한 설명은 앞 장에서 설명했으니 넘어가겠다.
링크(BFS): https://harley-hwan.github.io/2023-01-11-(46)DFS,BFS/
앞서 랜덤으로 미로를 생성하고, 우수법(오른손법칙)을 이용한 미로 찾기를 했었다.
이 방법은 최단 거리라는 것을 보장할 수 없으므로, 이번에는 최단 거리를 보장하는 너비 우선 탐색(BFS, Breath-First Search)으로 미로 찾기를 해보자.
링크(미로생성): https://harley-hwan.github.io/2022-03-30-(43)RightHandRule/
##
- BFS의 개념에 따라 갈 수 있는 모든 경로를 찾아 해당 좌표마다 부모 노드(출발지) 좌표 정보를 저장해둔다.
- 최종 도착지로부터 좌표의 출발지 좌표를 따라 List에 저장한다.
- List를 Reverse() 하여 역순으로 길을 찾는다.
##
BFS
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
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 (nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _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();
}
###
Board.cs
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class Board
{
const char CIRCLE = '\u25cf';
public TileType[,] Tile { get; private set; } //배열
public int Size { get; private set; }
public int DestY { get; private set; }
public int DestX { get; private set; }
Player _player;
public enum TileType
{
Empty,
Wall,
}
public void Initialize(int size, Player player)
{
if (size % 2 == 0)
return;
_player = player;
Tile = new TileType[size, size];
Size = size;
DestY = Size - 2;
DestX = Size - 2;
// Mazes for Programmers
//GenerateByBinaryTree();
GenerateBySideWinder();
}
void GenerateBySideWinder()
{
// 일단 길을 다 막아버리는 작업
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
Tile[y, x] = TileType.Wall;
else
Tile[y, x] = TileType.Empty;
}
}
// 랜덤으로 우측 혹은 아래로 길을 뚫는 작업
Random rand = new Random();
for (int y = 0; y < Size; y++)
{
int count = 1; // 몇 개의 점을 연속으로 뚫었는지 확인하기 위함. (그 중에서 랜덤으로 하나를 뽑아야하므로)
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (y == Size - 2 && x == Size - 2) // 가장 오른쪽 아래 지점 도착
continue; // 더 이상 길을 뚫지 않음.
if (y == Size - 2) // 아래쪽 벽을 만났을 때
{
Tile[y, x + 1] = TileType.Empty; // 무조건 오른쪽으로 길을 뚫는다.
continue;
}
if (x == Size - 2) // 오른쪽 벽을 만났을 때
{
Tile[y + 1, x] = TileType.Empty; // 무조건 아래로 길을 뚫는다.
continue;
}
if (rand.Next(0, 2) == 0)
{
Tile[y, x + 1] = TileType.Empty;
count++;
}
else
{
int randomIndex = rand.Next(0, count); // 연속된 count 수 중의 하나를 선택
Tile[y + 1, x] = TileType.Empty;
count = 1; // 연속이 끝나면 초기화
}
}
}
}
void GenerateByBinaryTree()
{
// 일단 길을 다 막아버리는 작업
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
Tile[y, x] = TileType.Wall;
else
Tile[y, x] = TileType.Empty;
}
}
// 랜덤으로 우측 혹은 아래로 길을 뚫는 작업
Random rand = new Random();
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (y == Size - 2 && x == Size - 2) // 가장 오른쪽 아래 지점에 도착했을 때
continue; // 무조건 오른쪽으로 가게하던 것을 없앰.
if (y == Size - 2) // 아래쪽 벽을 만났을 때
{
Tile[y, x + 1] = TileType.Empty; // 무조건 오른쪽으로 가게함.
continue;
}
if (x == Size - 2) // 오른쪽 벽을 만났을 때
{
Tile[y + 1, x] = TileType.Empty; // 무조건 아래로 가게함.
continue;
}
if (rand.Next(0, 2) == 0)
{
Tile[y, x + 1] = TileType.Empty;
}
else
{
Tile[y + 1, x] = TileType.Empty;
}
}
}
}
public void Render() // 렌더링
{
ConsoleColor prevColor = Console.ForegroundColor;
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
// 플레이어 좌표를 갖고 와서, 그 좌표랑 현재 y, x가 일치하면 플레이어 전용 색상으로 표시
if (y == _player.PosY && x == _player.PosX)
Console.ForegroundColor = ConsoleColor.Blue;
else if (y == DestY && x == DestX)
Console.ForegroundColor = ConsoleColor.Yellow;
else
Console.ForegroundColor = GetTileColor(Tile[y, x]);
Console.Write(CIRCLE);
}
Console.WriteLine();
}
Console.ForegroundColor = prevColor;
}
ConsoleColor GetTileColor(TileType type)
{
switch (type)
{
case TileType.Empty:
return ConsoleColor.Green;
case TileType.Wall:
return ConsoleColor.Red;
default:
return ConsoleColor.Green;
}
}
}
}
Player.cs
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class Pos
{
public Pos(int y, int x) { Y = y; X = x; }
public int Y;
public int X;
}
class Player
{
public int PosX { get; private set; } // Player 좌표는 Player만 고칠 수 있다.
public int PosY { 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 (nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _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 }; // Up, Left, Down, Right
int[] frontX = new int[] { 0, -1, 0, 1 };
int[] rightY = new int[] { 0, -1, 0, 1 }; // Up, Left, Down, Right
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)
{
// 오른쪽 방향으로 90도 회전 후
_dir = (_dir - 1 + 4) % 4;
// 앞으로 한 보 전진
PosY += frontY[_dir];
PosX += frontX[_dir];
_points.Add(new Pos(PosY, PosX));
}
// 2. 현재 바라보는 방향을 기준으로 전진할 수 있는지 확인
else if (_board.Tile[PosY + frontY[_dir], PosX + frontX[_dir]] == Board.TileType.Empty)
{
// 앞으로 한 보 전진
PosY += frontY[_dir];
PosX += frontX[_dir];
_points.Add(new Pos(PosY, PosX));
}
else
{
// 왼쪽 방향으로 90도 회전 (왼쪽 두번 회전하면 후진이 됨)
_dir = (_dir + 1 + 4) % 4;
}
}
}
const int MOVE_TICK = 10;
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
return;
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK)
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
}
Program.cs
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
using System;
namespace Algorithm
{
class Program
{
static void Main(string[] args)
{
Board board = new Board();
Player player = new Player();
board.Initialize(25, player);
player.Initialize(1, 1, board);
Console.CursorVisible = false;
const int WAIT_TICK = 1000 / 30;
//const char CIRCLE = '\u25cf';
int lastTick = 0;
while (true)
{
#region 프레임 관리
// FPS 프레임 (60프레임 OK, 30프레임 이하 NO) : 1초에 몇번 동작하는가
int currentTick = System.Environment.TickCount;
int elapsedTick = currentTick - lastTick; // 경과한 시간
// 만약에 경과한 시간이 1/30초보다 작다면
if (elapsedTick < WAIT_TICK)
continue;
int deltaTick = currentTick - lastTick; // 경과한 시간.
lastTick = currentTick;
#endregion
// 입력
// 로직
player.Update(deltaTick);
// 렌더링
Console.SetCursorPosition(0, 0);
board.Render();
}
}
}
}
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.