■ 개요
우리가 흔히 알고 있는 그래프 탐색 알고리즘에는 깊이우선탐색(DFS), 너비우선탐색(BFS), 다익스트라(Dijkstra) 알고리즘 등이 있다. 그렇다면 이런 그래프 탐색 알고리즘이 "2차원 배열의 타일맵(TileMap)"에서 어떻게 최단 경로를 찾는 데 사용될 수 있을까?
결론부터 말하자면, TileMap도 그래프이다. 예를 들어, 타일을 상하좌우 4방향으로만 이동할 수 있고, 흰색 타일을 길, 검은 타일을 장애물이라 하자. 이 경우, A타일은 인접한 B,C,D타일로 이동할 수 있다. 이런 타일을 그래프의 노드로 표현하면, A노드는 B,C,D를 자식 노드로 가지고 있는 것과 동일한 구조로 볼 수 있다.
- 즉, 각 타일은 그래프의 정점, 이동 가능한 인접한 타일은 간선으로 연결되어 있는 그래프이다.
- 이동할 때 특정 비용이 소모된다면, 가중치 있는 그래프로 표현할 수 있다.
따라서, 타일맵에서의 경로 탐색 문제는 그래프 탐색 문제로 완전히 환원될 수 있기 때문에 BFS, 다익스트라와 같은 알고리즘을 그대로 적용할 수 있다.
■ BFS로 최단 경로 찾기
그러면 BFS(너비 우선 탐색)을 사용해서 최단 경로를 찾아보자. BFS는 가중치를 고려하지 않기 때문에 모든 간선의 가중치가 동일한 그래프에서만 "최단 거리(이동 횟수 기준)"를 정확히 구할 수 있다.
BFS는 Queue를 사용해 구현하기 때문에, 위 그림처럼 "인접한 노드"를 우선으로 탐색하게 된다. 따라서 간선 수를 기준으로 가장 짧은 경로를 보장한다. BFS에 개념에 대해 간단하게 알아봤으니 이제 실제 구현으로 넘어가보자.
- DFS : Stack(FILO)을 사용하기 때문에 가장 깊은곳을 찍고 돌아온다. 따라서 탐색 순서가 2->7->10->11로 우연히 짧은 경로가 나올 수 있지만 이를 보장하진 않는다.
- BFS : Queue(FIFO)을 사용하기 때문에 인접한 노드를 먼저 탐색한다. 따라서 탐색 순서가 2->8->11로 간선 수를 기준으로 가장 짧은 경로를 보장한다.
일반적인 BFS의 시간복잡도는 V(노드 수), E(간선 수)라 했을 때 O(V+E)이다. 2차원 타일맵에서도 다음과 같이 계산할 수 있다.
- 노드 수 V = N(가로) X M(세로)
- 간선 수 E ≈ 4(8방향 이동 시 8V)
따라서 시간복잡도는 O(N * M)이 된다.
1. Parent[ , ]
최단 경로를 찾기 위해서는 각 노드(타일)가 어느 노드로부터 탐색되었는지, 즉 부모 노드 정보를 저장해야 한다. 그래야 도착 지점에 도달했을 때, 거슬러 올라가며 시작 지점까지의 경로를 복원할 수 있다.
좌표는 2차원 배열 인덱스를 기준으로 (y, x) 형식으로 기록하며, 탐색 과정은 다음과 같다.
- 노드 A(1,1)는 Start노드로부터 탐색되었기 때문에, A노드에는 Start노드의 위치(2,1)를 기록한다.
- 노드 B(0,1)는 A노드로부터 탐색되었기 때문에, B노드에는 A노드의 위치를 기록한다.
- 도착 지점을 찾을 때까지 기록한 뒤, 도착 지점을 찾으면 거슬러 올라가 시작 위치까지의 경로를 저장한다.
2. BFS 최단 경로 탐색 구현
BFS는 다음과 같은 방식으로 동작한다.
- 시작 노드를 Queue에 삽입.
- Queue에서 노드를 꺼낸다.
- 해당 노드의 인접 노드 중, 방문하지 않았거나 이동 가능한 노드를 Queue에 삽입하고 방문 처리한다..
- 도착 지점을 찾거나, 큐가 빌 때까지 2~3번 과정을 반복한다.
🛠 필요한 변수부터 정의.
- int tile[,] : 해당 위치가 벽인지(0), 길인지(1)를 저장할 2차원 배열. 인덱스가 해당 타일의 좌표(y,x)를 의미한다.
- bool visited[,] : 해당 노드를 방문했는지 저장할 배열.
- (int,int) parent[,] : 해당 인덱스 위치의 노드가 어느 노드로부터 탐색되었는지 저장.
public static class PathUtils
{
public static readonly Vector2Int[] SearchDir = new[]
{
new Vector2Int(0, -1), new Vector2Int(0, 1),
new Vector2Int(-1, 0), new Vector2Int(1, 0),
new Vector2Int(-1, -1), new Vector2Int(-1, 1),
new Vector2Int(1, -1), new Vector2Int(1, 1)
};
}
public class BFS
{
public List<(int, int)> BFS_PathFinding(int[,] tile, (int, int) start,
(int, int) end)
{
var visited = new bool[tile.GetLength(0), tile.GetLength(1)];
var queue = new Queue<(int, int)>();
var parent = new (int, int)[tile.GetLength(0), tile.GetLength(1)];
queue.Enqueue(start);
visited[start.Item1, start.Item2] = true;
while (queue.Count > 0)
{
var node = queue.Dequeue();
if(node == end)
{
return FindPath.FindShortPath(parent, start, end);
}
}
return null;
}
}함수의 파라미터로는 tile정보, 시작위치, 종료 위치를 받는다. 또한 인접한 노드를 편하게 탐색하기 위해(대각선 방향 포함) 다음과, 같이 탐색을 위한 배열을 마련해주었다(SearchDir 배열).
| 방향 | 상(↑) | 하(↓) | 좌(←) | 우(→) | 좌상(↖) | 좌하(↙) | 우상(↗) | 우하(↘) |
| x | 0 | 0 | -1 | +1 | -1 | -1 | +1 | +1 |
| y | -1 | +1 | 0 | 0 | -1 | 1 | -1 | 1 |
public List<(int, int)> BFS_PathFinding(int[,] tile, (int, int) start,
(int, int) end)
{
var visited = new bool[tile.GetLength(0), tile.GetLength(1)];
var queue = new Queue<(int, int)>();
var parent = new (int, int)[tile.GetLength(0), tile.GetLength(1)];
queue.Enqueue(start);
visited[start.Item1, start.Item2] = true;
while (queue.Count > 0)
{
var node = queue.Dequeue();
if (node == end)
{
return PathUtils.FindShortPath(parent, start, end);
}
var cnt = -1;
foreach (var dir in PathUtils.SearchDir)
{
cnt++;
var yPos = node.Item1 + dir.y;
var xPos = node.Item2 + dir.x;
if (xPos < 0 || xPos >= tile.GetLength(1) || yPos < 0 ||
yPos >= tile.GetLength(0))
{
continue;
}
if (tile[yPos, xPos] == 0 || visited[yPos, xPos] == true)
{
continue;
}
if (cnt >= 4 && PathUtils.IsDiagonalBlocked(tile, node,
(dir.y, dir.x)) == true)
{
continue;
}
queue.Enqueue((yPos, xPos));
visited[yPos, xPos] = true;
parent[yPos, xPos] = node;
}
}
return null;
}
}
현재 탐색 중인 노드(Dequeue된 요소)에 대해, 8방향(상, 하, 좌, 우 + 대각선)으로 인접한 노드로의 이동 가능 여부를 확인한다.
- 현재 노드 좌표에 dx, dy를 더한 결과가 맵 범위를 벗어나는 경우, 이동이 불가능하므로 continue.
- 이동하려는 위치가 벽(값이 0) 이거나, 이미 방문한 노드라면 continue.
- cnt >= 4인 경우는 대각선 방향 탐색을 의미한다. 이 경우, 대각선 이동 시 양옆이 모두 벽이라면 꼬이는 경로가 생길 수 있으므로 IsDiagonalBlocked()로 예외 처리를 한다.
※ 만약 상하좌우(4방향) 이동만 허용한다면 이 과정은 필요 없다.
최종적으로 이동이 가능하다면, queue에 넣고 부모 노드를 기록한 뒤 방문 처리한다.
3. 대각선 이동 예외 처리
만약 이동하려는 타일의 인접한 타일이 벽이라면, 위와 같은 이동은 불가능하다(벽을 뚫고 이동하기 때문). 따라서 대각선 이동 시, 이동하려는 타일의 인접한 노드가 벽이 아닌 경우에만 queue에 노드를 넣는다.
public static class PathUtils
{
public static bool IsDiagonalBlocked(int[,] tile, (int y, int x) curNode,
(int y, int x) moveDir)
{
var xPos = curNode.x + moveDir.x;
var yPos = curNode.y + moveDir.y;
if (xPos < 0 || xPos >= tile.GetLength(1) || yPos < 0 || yPos >= tile.GetLength(0))
return true;
return tile[yPos, curNode.x] == 0 &&
tile[curNode.y, xPos] == 0;
}
}
예를 들어, 현재 파란색 노드에서 오른쪽 위 방향(↗)에 있는 A 노드로 이동하려고 한다면, moveDir의 값은 (-1, +1)이 된다. 이때 이동이 유효한지 확인하기 위해 다음 두 위치를 검사해야 한다.
- [yPos, curNode.x] → 위쪽 방향(↑) 타일
- [curNode.y, xPos] → 오른쪽 방향(→) 타일
이 두 타일 모두 벽이라면, 해당 대각선 이동은 불가능하다고 판단하고 continue한다.
만약, 통로 폭이 한칸인 상황에서 다음과 같은 이동을 막고싶다면 앞의 AND연산을 OR연산으로 바꿔주면 된다.
4. 경로 복원
public static class PathUtils
{
public static List<(int, int)> FindShortPath((int, int)[,] parent, (int, int) start,
(int, int) end)
{
var result = new List<(int, int)>();
var current = end;
while (current != start)
{
result.Add(current);
current = parent[current.Item1, current.Item2];
}
result.Add(start);
result.Reverse();
return result;
}
}
도착 지점부터 시작 지점까지 부모 노드를 따라가며 경로를 List에 추가한다.이렇게 하면 경로가 도착 → 시작 순서로 저장되므로, Reverse()를 호출하여 시작 → 도착 순서로 바꿔준다.
추가로 지금은 경로가 무조건 존재하는 상황에서 작성한 코드이다. 만약, 경로가 존재하지 않을 수도 있다면 parent[current.y, current.x] == current등의 추가 조건을 넣어도 된다.
■ 전체 코드 및 결과
public static class PathUtils
{
public static readonly Vector2Int[] SearchDir = new[]
{
new Vector2Int(0, -1), new Vector2Int(0, 1),
new Vector2Int(-1, 0), new Vector2Int(1, 0),
new Vector2Int(-1, -1), new Vector2Int(-1, 1),
new Vector2Int(1, -1), new Vector2Int(1, 1)
};
public static List<(int, int)> FindShortPath((int, int)[,] parent, (int, int) start,
(int, int) end)
{
var result = new List<(int, int)>();
var current = end;
while (current != start)
{
result.Add(current);
current = parent[current.Item1, current.Item2];
}
result.Add(start);
result.Reverse();
return result;
}
public static bool IsDiagonalBlocked(int[,] tile, (int y, int x) curNode, (int y, int x) moveDir)
{
var xPos = curNode.x + moveDir.x;
var yPos = curNode.y + moveDir.y;
if (xPos < 0 || xPos >= tile.GetLength(1) || yPos < 0 || yPos >= tile.GetLength(0))
return true;
return tile[yPos, curNode.x] == 0 &&
tile[curNode.y, xPos] == 0;
}
}
public class BFS
{
public List<(int, int)> BFS_PathFinding(int[,] tile, (int, int) start,
(int, int) end)
{
var visited = new bool[tile.GetLength(0), tile.GetLength(1)];
var queue = new Queue<(int, int)>();
var parent = new (int, int)[tile.GetLength(0), tile.GetLength(1)];
queue.Enqueue(start);
visited[start.Item1, start.Item2] = true;
while (queue.Count > 0)
{
var node = queue.Dequeue();
if (node == end)
{
return PathUtils.FindShortPath(parent, start, end);
}
var cnt = -1;
foreach (var dir in PathUtils.SearchDir)
{
cnt++;
var yPos = node.Item1 + dir.y;
var xPos = node.Item2 + dir.x;
if (xPos < 0 || xPos >= tile.GetLength(1) || yPos < 0 ||
yPos >= tile.GetLength(0))
{
continue;
}
if (tile[yPos, xPos] == 0 || visited[yPos, xPos] == true)
{
continue;
}
if (cnt >= 4 && PathUtils.IsDiagonalBlocked(tile, node,
(dir.y, dir.x)) == true)
{
continue;
}
queue.Enqueue((yPos, xPos));
visited[yPos, xPos] = true;
parent[yPos, xPos] = node;
}
}
return null;
}
}'Unity,C# > 알고리즘' 카테고리의 다른 글
| [정렬 알고리즘, C#] 버블 정렬(Bubble Sort) (1) | 2025.06.17 |
|---|---|
| [C#, Unity, 최단경로(PathFinding)] TileMap A* 알고리즘 (0) | 2025.04.10 |
| [C#, Unity, 최단경로(PathFinding)] TileMap 다익스트라(Dijkstra) 알고리즘 (0) | 2025.04.10 |
| [C#, Algorithm] Dynamic Programming(동적 계획법) (0) | 2025.04.10 |
| [C#, Algorithm] 그라디(탐욕, 욕심쟁이) 알고리즘 (2) | 2025.04.10 |