내일배움캠프 66일차 TIL - 비선형 자료구조 Graph
확인 문제
1. Graph가 무엇인지 알고 있나요?
내 답:
그래프(Graph)는 노드(Node) 또는 정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된 자료구조입니다. 그래프는 네트워크 모델을 표현하는 데 사용되며, 여러 가지 문제를 모델링하고 해결하는 데 널리 사용됩니다. 그래프는 방향성이 있는 방향 그래프(Directed Graph)와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉩니다. 또한, 간선에 가중치가 부여된 가중 그래프(Weighted Graph)와 가중치가 없는 비가중 그래프(Unweighted Graph)로 구분될 수 있습니다.
모범 답:
2. Tree는 Graph인가요? Graph는 Tree인가요?
내 답:
• Tree는 Graph입니다: 트리(Tree)는 사이클이 없는 연결 그래프(Connected Graph)의 한 종류로, 특별한 형태의 그래프입니다. 트리는 한 개의 루트 노드를 가지며, 모든 자식 노드는 단 하나의 부모 노드만을 가집니다. 트리는 계층적인 구조를 가지며, 그래프의 특수한 경우로 볼 수 있습니다.
• Graph는 항상 Tree가 아닙니다: 모든 그래프가 트리인 것은 아닙니다. 트리가 되기 위해서는 그래프가 연결되어 있어야 하며(Connected), 사이클이 없어야 합니다(Acyclic). 또한, 모든 노드는 다른 모든 노드와 정확히 하나의 경로로만 연결되어야 합니다. 이러한 조건을 만족하지 않는 그래프는 트리가 아닙니다.
모범 답:
3. NavMesh가 길찾기를 위해 사용하는 알고리즘은 무엇인가요?
내 답:
NavMesh를 사용한 길찾기 알고리즘으로는 A (A-star) 알고리즘과 Dijkstra의 알고리즘이 일반적으로 사용됩니다. A 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 사용되며, 휴리스틱(Heuristic)을 사용하여 탐색의 효율성을 높입니다. Dijkstra의 알고리즘은 모든 노드 간의 최단 경로를 찾는 데 사용되지만, A* 알고리즘에 비해 탐색 속도가 느릴 수 있습니다. NavMesh와 함께 이러한 알고리즘을 사용하면, 게임 내 캐릭터가 장애물을 피하면서 효율적으로 목적지까지 이동할 수 있습니다.
모범 답:
설명 문제
1. 길찾기 알고리즘에 대해 알고 있는 것이 있나요?
내 답:
길찾기(Pathfinding) 알고리즘은 두 지점 사이의 최적 경로를 찾는 데 사용되는 알고리즘입니다. 대표적인 길찾기 알고리즘으로는 Dijkstra의 알고리즘, A* (A-star) 알고리즘, 벨만-포드 알고리즘, 그리디 베스트-퍼스트 탐색 등이 있습니다.
모범 답:
2. 각 길찾기 알고리즘의 차이점은 무엇인가요?
내 답:
• Dijkstra의 알고리즘: 모든 노드 간의 최단 경로를 찾습니다. 가중치가 있는 그래프에서 사용할 수 있으며, 가중치는 음수가 아니어야 합니다. 탐색 과정에서 방문하지 않은 모든 노드를 고려하기 때문에 비교적 느릴 수 있습니다.
• A 알고리즘: 시작 노드에서 목표 노드까지의 최단 경로를 찾습니다. 휴리스틱 함수를 사용하여 탐색의 효율성을 높입니다. Dijkstra의 알고리즘보다 더 빠르게 목표에 도달할 수 있습니다.
• 벨만-포드 알고리즘: 가중치가 음수인 간선이 포함된 그래프에서도 사용할 수 있습니다. 모든 노드 간의 최단 경로를 찾으며, 음수 사이클의 존재도 검출할 수 있습니다. 대규모 그래프에서는 비효율적일 수 있습니다.
• 그리디 베스트-퍼스트 탐색: 휴리스틱을 사용하여 목표 노드 방향으로 탐색을 진행합니다. A 알고리즘보다 더 빠르게 탐색을 진행할 수 있지만, 항상 최단 경로를 보장하지는 않습니다.
모범 답:
3. A* 알고리즘에 대해 설명해주세요.
내 답:
A 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 사용되는 효율적인 탐색 알고리즘입니다. 각 노드에 대해 f(n) = g(n) + h(n)의 값을 계산하여 탐색을 진행합니다. 여기서 g(n)은 시작 노드부터 노드 n까지의 실제 비용, h(n)은 노드 n부터 목표 노드까지의 예상 비용(휴리스틱)을 나타냅니다. A 알고리즘은 이 f(n) 값을 최소화하는 경로를 찾아냄으로써 효율적으로 목표에 도달합니다. 휴리스틱 함수의 선택이 알고리즘의 효율성에 큰 영향을 미칩니다.
모범 답:
4. 해당 알고리즘들을 프로젝트에 적용해본 경험이 있나요?
내 답:
제가 했었던 팀 프로젝트에서 유닛들을 계속해서 이동시키며 적절한 위치에 배치를 할 필요성이 있었습니다. 이에 NevMesh와 A* 알고리즘을 이용해 적절한 이동을 구현했던 기억이 있습니다.
모범 답:
실습 문제
💡 **[A* 알고리즘 직접 구현해보기]**A* 알고리즘을 이용하여 플레이어가 현재 위치에서 목표 위치까지의 최단 경로를 찾고 출력하는 코드를 작성하세요.
구현사항
-
PathFinding메서드: A* 알고리즘 구현. -
입력 매개 변수:
Board board- 맵 객체Block start- 시작 블록Block dest- 목표 블록
-
반환값:
Block- 시작 블록을 반환하여 경로를 나타냄. 경로를 찾지 못하면null을 반환. -
초기 조건 확인 및 변수 초기화:
- 맵에서 시작 블록과 목표 블록의 존재 여부를 확인합니다.
- 모든 블록의 상태를 초기화합니다.
- 대기 목록과 검사 완료 목록을 초기화합니다.
- 현재 블록을 시작 블록으로 설정합니다.
-
경로 탐색 루프:
- 현재 블록의 주변 블록을 가져옵니다.
- 주변 블록을 대기 목록에 추가합니다.
- 현재 블록을 검사 완료 목록에 추가하고, 대기 목록에서 제거합니다.
- 만약 주변에 이동 가능한 블록이 없다면 경로 탐색을 중단합니다.
- 주변 블록들의 G, H 값을 계산합니다.
- 다음 검사할 블록을 선택합니다.
- 만약 다음 검사할 블록이 없다면, 대기 목록에서 F 값이 가장 낮은 블록을 선택합니다.
- 목표 블록에 도착한 경우 탐색을 종료합니다.
-
경로 역추적:
- 탐색이 끝나면 목표 블록에서 시작 블록으로 경로를 역추적합니다.
- 경로를 설정하여 반환합니다.
주요 클래스와 메서드
-
AStar클래스:GetPriorityBlock- 대기 목록에 있는 블록들 중에서 F 값(총 비용)이 가장 낮은 블록을 선택하여 반환합니다.
- F 값이 낮을수록 해당 블록이 목적지에 가까운 경로에 위치해 있음을 의미합니다.
GetNextBlock- 현재 블록의 주변 블록들 중에서 검사되지 않은 블록 중 H 값이 가장 낮은 블록을 선택하여 반환합니다.
CalcRating- 주변 블록들의 G, H, F 값을 계산하고 설정합니다. G 값은 시작점부터 현재 블록까지의 비용을 나타내며, H 값은 현재 블록에서 목표 블록까지의 휴리스틱 비용을 나타냅니다. F 값은 G와 H의 합으로, 경로 탐색의 우선순위를 결정하는 데 사용됩니다.
-
Board클래스:CheckClear메서드: 블록 상태 초기화.Exists메서드: 블록 존재 여부 확인.GetNode메서드: 특정 좌표의 블록 반환.GetAroundBlocks메서드: 주변 블록 반환.
-
Block클래스:
-SetPrice메서드: G와 H 값 설정.
-Clear메서드: 블록 상태 초기화.
-Equals메서드: 블록 좌표 비교.
public class Program
{
static void Main(string[] args)
{
char[,] map = {
{'□', '□', '□', '□', '□'},
{'□', '■', '■', '□', '□'},
{'□', '□', '□', '□', '□'},
{'□', '□', '■', '■', '□'},
{'□', '□', '□', '□', '□'}
};
for (int i = 0; i < map.GetLength(0); i++)
{
for (int j = 0; j < map.GetLength(1); j++)
Console.Write(map[i, j]);
Console.WriteLine();
}
Console.WriteLine("현재 플레이어 위치를 입력하세요 (a, b):");
int a = int.Parse(Console.ReadLine());
int b = int.Parse(Console.ReadLine());
Console.WriteLine("목표 위치를 입력하세요 (x, y):");
int x = int.Parse(Console.ReadLine());
int y = int.Parse(Console.ReadLine());
Board board = new Board(map);
Block start = board.GetNode(a, b);
Block dest = board.GetNode(x, y);
Block path = AStar.PathFinding(board, start, dest);
if (path != null)
{
Console.WriteLine("최단 경로:");
while (path != null)
{
Console.Write($"({path.x}, {path.y}) ");
path = path.next;
}
}
else
{
Console.WriteLine("경로를 찾을 수 없습니다.");
}
}
}
public static class AStar
{
public static Block PathFinding(Board board, Block start, Block dest)
{
// TODO : A* 알고리즘 직접 구현
}
private static Block GetPriorityBlock(List<Block> waittingBlocks)
{
Block block = null;
var enumerator = waittingBlocks.GetEnumerator();
while (enumerator.MoveNext())
{
var current = enumerator.Current;
if (block == null || block.F > current.F)
{
block = current;
}
}
return block;
}
private static Block GetNextBlock(List<Block> arounds, Block current)
{
Block minValueBlock = null;
for (int i = 0; i < arounds.Count; i++)
{
Block next = arounds[i];
if (!next.check)
{
if (minValueBlock == null)
{
minValueBlock = next;
}
else if (minValueBlock.H > next.H)
{
minValueBlock = next;
}
}
}
return minValueBlock;
}
private static void CalcRating(List<Block> arounds, Block start, Block current, Block dest)
{
if (arounds != null)
{
for (int i = 0; i < arounds.Count; i++)
{
var block = arounds[i];
bool isDiagonalBlock = Math.Abs(block.x - current.x) == 1 && Math.Abs(block.y - current.y) == 1;
int priceFromDest = (Math.Abs(dest.x - block.x) + Math.Abs(dest.y - block.y)) * 10;
if (block.prev == null)
block.prev = current;
block.SetPrice(current.G + (isDiagonalBlock ? 14 : 10), priceFromDest);
}
}
}
}
public class Board
{
public Block[,] blocks;
public Board(char[,] map)
{
int width = map.GetLength(0);
int height = map.GetLength(1);
blocks = new Block[width, height];
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
blocks[i, j] = new Block(i, j, map[i, j] == '■');
}
}
}
public void CheckClear()
{
foreach (Block block in blocks)
{
block.Clear();
}
}
public bool Exists(Block block)
{
return Exists(block.x, block.y);
}
public bool Exists(int x, int y)
{
return x >= 0 && x < blocks.GetLength(0) && y >= 0 && y < blocks.GetLength(1);
}
public Block GetNode(int x, int y)
{
return blocks[x, y];
}
public List<Block> GetAroundBlocks(Block target)
{
List<Block> arounds = new List<Block>();
if (Exists(target.x - 1, target.y - 1))
{
Block block = blocks[target.x - 1, target.y - 1];
arounds.Add(block);
}
if (Exists(target.x, target.y - 1))
{
Block block = blocks[target.x, target.y - 1];
arounds.Add(block);
}
if (Exists(target.x + 1, target.y - 1))
{
Block block = blocks[target.x + 1, target.y - 1];
arounds.Add(block);
}
if (Exists(target.x - 1, target.y))
{
Block block = blocks[target.x - 1, target.y];
arounds.Add(block);
}
if (Exists(target.x + 1, target.y))
{
Block block = blocks[target.x + 1, target.y];
arounds.Add(block);
}
if (Exists(target.x - 1, target.y + 1))
{
Block block = blocks[target.x - 1, target.y + 1];
arounds.Add(block);
}
if (Exists(target.x, target.y + 1))
{
Block block = blocks[target.x, target.y + 1];
arounds.Add(block);
}
if (Exists(target.x + 1, target.y + 1))
{
Block block = blocks[target.x + 1, target.y + 1];
arounds.Add(block);
}
for (int i = arounds.Count - 1; i >= 0; i--)
{
Block block = arounds[i];
bool isDiagonalBlock = Math.Abs(block.x - target.x) == 1 && Math.Abs(block.y - target.y) == 1;
if (isDiagonalBlock)
{
Block blockX = arounds.Find(b => b.x == block.x && b.y == target.y);
if (blockX != null && blockX.wall)
arounds.Remove(block);
Block blockY = arounds.Find(b => b.x == target.x && b.y == block.y);
if (blockY != null && blockY.wall)
arounds.Remove(block);
}
}
arounds.RemoveAll(b => b.wall);
return arounds;
}
}
public class Block
{
public int x, y;
public bool wall;
public int F => G + H;
public int G { get; private set; } = 0;
public int H { get; private set; } = 0;
public bool check = false;
public Block prev = null;
public Block next = null;
public Block(int x, int y, bool wall = false)
{
this.x = x;
this.y = y;
this.wall = wall;
}
public void SetPrice(int g, int h)
{
this.G = g;
this.H = h;
}
public void Clear()
{
check = false;
G = 0;
H = 0;
prev = null;
next = null;
}
public override bool Equals(object obj)
{
if (obj is Block other)
{
return x == other.x && y == other.y;
}
return false;
}
}
