알고리즘 — 그래프(Graph)와 BFS / DFS

개요 — 왜 그래프 알고리즘을 알아야 하는가

그래프(Graph)는 게임 개발에서 가장 범용적으로 사용되는 자료구조입니다.

• AI 캐릭터가 맵을 이동하는 NavigationMesh 경로탐색
• 스킬 트리, 퀘스트 체인의 선후 관계(의존성) 그래프
• 온라인 게임의 플레이어 소셜 네트워크 (친구 관계, 길드)
• 인터랙티브 오브젝트 간 이벤트 연결 다이어그램

이 글에서는 그래프의 기본 개념부터 BFS, DFS, 다익스트라 알고리즘의 C++ 구현, 그리고 Unreal Engine 5에서의 실전 적용 패턴을 체계적으로 학습합니다.

---

1. 그래프의 기본 개념

1.1 정점과 간선

그래프 G = (V, E)는 정점(Vertex/Node) 의 집합 V와 간선(Edge) 의 집합 E로 구성됩니다.

    A --- B
    |     |
    C --- D

• 정점(V): A, B, C, D — 데이터를 담는 단위 (맵의 웨이포인트, 스킬 노드 등)
• 간선(E): A-B, A-C, B-D, C-D — 정점 간의 관계 또는 경로

1.2 방향 그래프 vs 무방향 그래프

구분	설명	예시
무방향 그래프(Undirected)	간선에 방향 없음, A-B = B-A	양방향 통행로, 친구 관계
방향 그래프(Directed / Digraph)	간선에 방향 있음, A→B ≠ B→A	퀘스트 선행 조건, 스킬 트리

// 무방향: A — B (양방향 이동 가능)
// 방향:   A → B (A에서 B로만 이동 가능)

1.3 가중치 그래프

간선에 가중치(Weight) 를 부여한 그래프입니다. 게임에서는 이동 비용, 거리, 통행료 등을 표현합니다.

    A --5-- B
    |       |
    3       2
    |       |
    C --8-- D

A에서 D까지 최단 경로: A→B→D (비용 7) vs A→C→D (비용 11)

1.4 그래프 표현 방식: 인접 행렬 vs 인접 리스트

인접 행렬(Adjacency Matrix)

V×V 크기의 2차원 배열. matrix[i][j] = 1이면 i→j 간선 존재.

// 정점 4개 (0~3)의 인접 행렬
int AdjMatrix[4][4] = {
    {0, 1, 1, 0},  // 0: 1, 2와 연결
    {1, 0, 0, 1},  // 1: 0, 3과 연결
    {1, 0, 0, 1},  // 2: 0, 3과 연결
    {0, 1, 1, 0}   // 3: 1, 2와 연결
};

• 조회: O(1) — i-j 간선 존재 여부를 즉시 확인
• 공간: O(V²) — 정점 수가 많으면 비효율적 (희소 그래프에 부적합)
• 용도: 정점 수가 적고 간선이 밀집된 그래프

인접 리스트(Adjacency List)

각 정점마다 연결된 정점 목록을 벡터로 관리.

#include <vector>

// 정점 4개의 인접 리스트
std::vector<std::vector<int>> AdjList(4);

// 간선 추가 (무방향)
auto AddEdge = [&](int U, int V)
{
    AdjList[U].push_back(V);
    AdjList[V].push_back(U);
};

AddEdge(0, 1);
AddEdge(0, 2);
AddEdge(1, 3);
AddEdge(2, 3);
// AdjList[0] = {1, 2}
// AdjList[1] = {0, 3}
// AdjList[2] = {0, 3}
// AdjList[3] = {1, 2}

• 조회: O(degree(V)) — 이웃 정점 수에 비례
• 공간: O(V+E) — 실제 간선 수만큼만 사용
• 용도: 대부분의 실전 그래프 (희소 그래프에 효율적)

구분	인접 행렬	인접 리스트
공간 복잡도	O(V²)	O(V+E)
간선 확인	O(1)	O(degree)
이웃 순회	O(V)	O(degree)
적합한 경우	밀집 그래프	희소 그래프 (대부분의 경우)

---

2. BFS (너비 우선 탐색, Breadth-First Search)

2.1 개념과 원리

BFS는 시작 정점에서 거리가 가까운 정점부터 차례대로 방문하는 탐색 방식입니다. 큐(Queue) 를 사용하여 구현합니다.

탐색 순서 (시작: A):
    A
   / \
  B   C
 / \   \
D   E   F

방문 순서: A → B → C → D → E → F

핵심 특성:

• 큐 기반 (FIFO — 먼저 발견한 정점부터 처리)
• 시간 복잡도: O(V + E) — 모든 정점과 간선을 한 번씩 방문
• 최단 경로 보장 — 가중치 없는 그래프에서 시작점으로부터의 최단 거리 탐색에 최적

2.2 C++ 구현

#include <iostream>
#include <vector>
#include <queue>

class FGraph
{
public:
    int VertexCount;
    std::vector<std::vector<int>> AdjList;

    explicit FGraph(int InVertexCount)
        : VertexCount(InVertexCount)
        , AdjList(InVertexCount)
    {
    }

    void AddEdge(int U, int V)
    {
        AdjList[U].push_back(V);
        AdjList[V].push_back(U); // 무방향 그래프
    }

    // BFS 탐색 — StartVertex에서 시작, 방문 순서 반환
    std::vector<int> BFS(int StartVertex) const
    {
        std::vector<bool> bVisited(VertexCount, false);
        std::vector<int> VisitOrder;
        std::queue<int> Queue;

        bVisited[StartVertex] = true;
        Queue.push(StartVertex);

        while (!Queue.empty())
        {
            int Current = Queue.front();
            Queue.pop();
            VisitOrder.push_back(Current);

            for (int Neighbor : AdjList[Current])
            {
                if (!bVisited[Neighbor])
                {
                    bVisited[Neighbor] = true;
                    Queue.push(Neighbor);
                }
            }
        }

        return VisitOrder;
    }

    // BFS 최단 경로 — StartVertex에서 각 정점까지의 최단 거리 반환
    std::vector<int> BFSShortestDistance(int StartVertex) const
    {
        constexpr int Unreachable = -1;
        std::vector<int> Distance(VertexCount, Unreachable);
        std::queue<int> Queue;

        Distance[StartVertex] = 0;
        Queue.push(StartVertex);

        while (!Queue.empty())
        {
            int Current = Queue.front();
            Queue.pop();

            for (int Neighbor : AdjList[Current])
            {
                if (Distance[Neighbor] == Unreachable)
                {
                    Distance[Neighbor] = Distance[Current] + 1;
                    Queue.push(Neighbor);
                }
            }
        }

        return Distance;
    }
};

int main()
{
    FGraph Graph(6);
    Graph.AddEdge(0, 1);
    Graph.AddEdge(0, 2);
    Graph.AddEdge(1, 3);
    Graph.AddEdge(1, 4);
    Graph.AddEdge(2, 5);

    // BFS 탐색 순서: 0 1 2 3 4 5
    std::vector<int> Order = Graph.BFS(0);

    // 최단 거리: [0]=0, [1]=1, [2]=1, [3]=2, [4]=2, [5]=2
    std::vector<int> Dist = Graph.BFSShortestDistance(0);

    return 0;
}

2.3 BFS 활용 — 연결 요소(Connected Components) 탐색

// 그래프 전체에서 연결된 구성 요소 수를 구하는 BFS
int CountConnectedComponents(const FGraph& Graph)
{
    std::vector<bool> bVisited(Graph.VertexCount, false);
    int ComponentCount = 0;

    for (int Vertex = 0; Vertex < Graph.VertexCount; ++Vertex)
    {
        if (!bVisited[Vertex])
        {
            // 새로운 연결 요소 발견
            ++ComponentCount;
            std::queue<int> Queue;
            Queue.push(Vertex);
            bVisited[Vertex] = true;

            while (!Queue.empty())
            {
                int Current = Queue.front();
                Queue.pop();

                for (int Neighbor : Graph.AdjList[Current])
                {
                    if (!bVisited[Neighbor])
                    {
                        bVisited[Neighbor] = true;
                        Queue.push(Neighbor);
                    }
                }
            }
        }
    }

    return ComponentCount;
}

---

3. DFS (깊이 우선 탐색, Depth-First Search)

3.1 개념과 원리

DFS는 시작 정점에서 한 방향으로 최대한 깊게 파고들다가, 더 이상 갈 수 없으면 돌아와 다른 경로를 탐색하는 방식입니다. 스택(Stack) 또는 재귀(Recursion) 로 구현합니다.

탐색 순서 (시작: A):
    A
   / \
  B   C
 / \   \
D   E   F

방문 순서: A → B → D → E → C → F

핵심 특성:

• 스택 기반 또는 재귀 호출 (LIFO — 가장 최근 발견 경로 우선)
• 시간 복잡도: O(V + E)
• 사이클 감지, 위상 정렬, 강한 연결 요소 탐색에 활용

3.2 C++ 구현 — 재귀 방식

class FGraph
{
public:
    // ... (위 BFS 구현과 동일한 멤버)

    // DFS 재귀 구현
    void DFSRecursive(int Vertex, std::vector<bool>& bVisited, std::vector<int>& VisitOrder) const
    {
        bVisited[Vertex] = true;
        VisitOrder.push_back(Vertex);

        for (int Neighbor : AdjList[Vertex])
        {
            if (!bVisited[Neighbor])
            {
                DFSRecursive(Neighbor, bVisited, VisitOrder);
            }
        }
    }

    std::vector<int> DFS(int StartVertex) const
    {
        std::vector<bool> bVisited(VertexCount, false);
        std::vector<int> VisitOrder;
        DFSRecursive(StartVertex, bVisited, VisitOrder);
        return VisitOrder;
    }
};

3.3 C++ 구현 — 반복(Stack) 방식

#include <stack>

std::vector<int> DFSIterative(int StartVertex) const
{
    std::vector<bool> bVisited(VertexCount, false);
    std::vector<int> VisitOrder;
    std::stack<int> Stack;

    Stack.push(StartVertex);

    while (!Stack.empty())
    {
        int Current = Stack.top();
        Stack.pop();

        if (bVisited[Current])
        {
            continue;
        }

        bVisited[Current] = true;
        VisitOrder.push_back(Current);

        // 역순으로 push하면 재귀 DFS와 동일한 방문 순서
        for (int i = static_cast<int>(AdjList[Current].size()) - 1; i >= 0; --i)
        {
            int Neighbor = AdjList[Current][i];
            if (!bVisited[Neighbor])
            {
                Stack.push(Neighbor);
            }
        }
    }

    return VisitOrder;
}

3.4 DFS 활용 — 사이클 감지 (방향 그래프)

방향 그래프에서 사이클을 감지하려면 현재 DFS 경로(재귀 스택) 에 있는 정점인지를 추적합니다.

// 방향 그래프에서 사이클 감지
// bInRecStack: 현재 DFS 재귀 경로에 있는 정점 표시
bool HasCycleDFS(int Vertex,
                 std::vector<bool>& bVisited,
                 std::vector<bool>& bInRecStack) const
{
    bVisited[Vertex] = true;
    bInRecStack[Vertex] = true;

    for (int Neighbor : AdjList[Vertex])
    {
        if (!bVisited[Neighbor])
        {
            if (HasCycleDFS(Neighbor, bVisited, bInRecStack))
            {
                return true;
            }
        }
        else if (bInRecStack[Neighbor])
        {
            // 현재 경로에 있는 정점으로 돌아옴 = 사이클 발견
            return true;
        }
    }

    bInRecStack[Vertex] = false; // 재귀 스택에서 제거
    return false;
}

bool HasCycle() const
{
    std::vector<bool> bVisited(VertexCount, false);
    std::vector<bool> bInRecStack(VertexCount, false);

    for (int Vertex = 0; Vertex < VertexCount; ++Vertex)
    {
        if (!bVisited[Vertex] && HasCycleDFS(Vertex, bVisited, bInRecStack))
        {
            return true;
        }
    }
    return false;
}

3.5 DFS 활용 — 위상 정렬 (Topological Sort)

방향 비순환 그래프(DAG)에서 선행 조건을 지키는 순서로 정점을 나열합니다. 퀘스트 선행 관계, 빌드 의존성 등에 활용됩니다.

// DFS 기반 위상 정렬
void TopologicalSortDFS(int Vertex,
                        std::vector<bool>& bVisited,
                        std::stack<int>& ResultStack) const
{
    bVisited[Vertex] = true;

    for (int Neighbor : AdjList[Vertex])
    {
        if (!bVisited[Neighbor])
        {
            TopologicalSortDFS(Neighbor, bVisited, ResultStack);
        }
    }

    // 모든 후행 정점을 처리한 뒤 스택에 추가
    ResultStack.push(Vertex);
}

std::vector<int> TopologicalSort() const
{
    std::vector<bool> bVisited(VertexCount, false);
    std::stack<int> ResultStack;

    for (int Vertex = 0; Vertex < VertexCount; ++Vertex)
    {
        if (!bVisited[Vertex])
        {
            TopologicalSortDFS(Vertex, bVisited, ResultStack);
        }
    }

    std::vector<int> Result;
    while (!ResultStack.empty())
    {
        Result.push_back(ResultStack.top());
        ResultStack.pop();
    }
    return Result; // 위상 정렬 결과
}

---

4. 다익스트라(Dijkstra) 알고리즘

4.1 개념

가중치 그래프에서 단일 출발점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (음수 가중치 불가)

• 시간 복잡도: O((V + E) log V) — 우선순위 큐(힙) 사용 시
• 우선순위 큐(min-heap) 로 현재까지 가장 비용이 낮은 정점을 먼저 처리

알고리즘 동작 원리:

1. 시작 정점의 거리를 0으로 설정, 나머지는 무한대(∞)로 초기화
2. 우선순위 큐에 시작 정점을 삽입
3. 큐에서 거리가 가장 짧은 정점 U를 꺼냄
4. U의 이웃 V에 대해: dist[U] + weight(U,V) < dist[V]이면 dist[V]를 갱신하고 큐에 삽입 (Relaxation)
5. 큐가 빌 때까지 반복

4.2 C++ 구현

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

// 가중치 그래프: {이웃 정점, 가중치}
using FWeightedEdge = std::pair<int, int>;
using FWeightedGraph = std::vector<std::vector<FWeightedEdge>>;

// {거리, 정점} — 우선순위 큐는 기본적으로 max-heap이므로
// pair 첫 번째 요소(거리)를 음수로 저장하거나 greater<> 사용
using FDistVertex = std::pair<int, int>;

std::vector<int> Dijkstra(const FWeightedGraph& Graph, int StartVertex)
{
    const int VertexCount = static_cast<int>(Graph.size());
    std::vector<int> Distance(VertexCount, INT_MAX);

    // min-heap: 거리가 작은 정점 우선 처리
    std::priority_queue<FDistVertex,
                        std::vector<FDistVertex>,
                        std::greater<FDistVertex>> MinHeap;

    Distance[StartVertex] = 0;
    MinHeap.push({0, StartVertex});

    while (!MinHeap.empty())
    {
        auto [CurrentDist, CurrentVertex] = MinHeap.top();
        MinHeap.pop();

        // 이미 더 짧은 경로로 처리된 정점은 스킵
        if (CurrentDist > Distance[CurrentVertex])
        {
            continue;
        }

        for (auto [Neighbor, Weight] : Graph[CurrentVertex])
        {
            int NewDist = Distance[CurrentVertex] + Weight;

            if (NewDist < Distance[Neighbor])
            {
                Distance[Neighbor] = NewDist;
                MinHeap.push({NewDist, Neighbor});
            }
        }
    }

    return Distance; // Distance[i] = StartVertex에서 i까지의 최단 거리
}

int main()
{
    // 5개 정점의 가중치 방향 그래프
    FWeightedGraph Graph(5);

    auto AddDirectedEdge = [&](int U, int V, int W)
    {
        Graph[U].push_back({V, W});
    };

    AddDirectedEdge(0, 1, 4);
    AddDirectedEdge(0, 2, 1);
    AddDirectedEdge(2, 1, 2);
    AddDirectedEdge(1, 3, 1);
    AddDirectedEdge(2, 3, 5);
    AddDirectedEdge(3, 4, 3);

    std::vector<int> Dist = Dijkstra(Graph, 0);
    // Dist[0]=0, Dist[1]=3, Dist[2]=1, Dist[3]=4, Dist[4]=7

    return 0;
}

4.3 경로 복원 (Path Reconstruction)

최단 거리뿐 아니라 실제 경로도 추적하려면 각 정점의 이전 정점(predecessor)을 기록합니다.

struct FDijkstraResult
{
    std::vector<int> Distance;
    std::vector<int> Previous; // Previous[V] = V에 도달하기 직전 정점
};

FDijkstraResult DijkstraWithPath(const FWeightedGraph& Graph, int StartVertex)
{
    const int VertexCount = static_cast<int>(Graph.size());
    FDijkstraResult Result;
    Result.Distance.assign(VertexCount, INT_MAX);
    Result.Previous.assign(VertexCount, -1);

    std::priority_queue<FDistVertex,
                        std::vector<FDistVertex>,
                        std::greater<FDistVertex>> MinHeap;

    Result.Distance[StartVertex] = 0;
    MinHeap.push({0, StartVertex});

    while (!MinHeap.empty())
    {
        auto [CurrentDist, CurrentVertex] = MinHeap.top();
        MinHeap.pop();

        if (CurrentDist > Result.Distance[CurrentVertex])
        {
            continue;
        }

        for (auto [Neighbor, Weight] : Graph[CurrentVertex])
        {
            int NewDist = Result.Distance[CurrentVertex] + Weight;

            if (NewDist < Result.Distance[Neighbor])
            {
                Result.Distance[Neighbor] = NewDist;
                Result.Previous[Neighbor] = CurrentVertex;
                MinHeap.push({NewDist, Neighbor});
            }
        }
    }

    return Result;
}

// 경로 복원: Target에서 Start까지 역추적
std::vector<int> ReconstructPath(const std::vector<int>& Previous, int Target)
{
    std::vector<int> Path;
    for (int Vertex = Target; Vertex != -1; Vertex = Previous[Vertex])
    {
        Path.push_back(Vertex);
    }
    std::reverse(Path.begin(), Path.end());
    return Path; // [Start, ..., Target]
}

---

5. 알고리즘 비교 요약

알고리즘	자료구조	시간 복잡도	가중치	주요 용도
BFS	Queue	O(V+E)	X	최단 경로(무가중치), 연결 요소
DFS	Stack / 재귀	O(V+E)	X	사이클 감지, 위상 정렬, 연결 요소
다익스트라	Min-Heap	O((V+E) log V)	O (양수)	최단 경로(가중치 그래프)
벨만-포드	배열	O(V·E)	O (음수 포함)	음수 가중치 최단 경로
A*	Min-Heap+Heuristic	O(E log V) 이하	O	목적지 지향 최단 경로

---

6. Unreal Engine에서의 실전 활용

6.1 NavigationMesh와 경로탐색

Unreal Engine의 UNavigationSystemV1은 내부적으로 NavMesh 위에서 A 알고리즘*(다익스트라의 휴리스틱 확장)으로 경로를 탐색합니다.

#include "NavigationSystem.h"
#include "NavigationPath.h"
#include "AI/NavigationSystemBase.h"

// AI 캐릭터가 목적지까지의 경로를 요청하는 예시
void AMyAICharacter::RequestPathTo(const FVector& Destination)
{
    UNavigationSystemV1* NavSystem =
        UNavigationSystemV1::GetCurrent(GetWorld());

    if (!NavSystem)
    {
        return;
    }

    FNavPathSharedPtr NavPath;
    FPathFindingQuery Query(this, *NavSystem->GetDefaultNavDataInstance(),
                            GetActorLocation(), Destination);

    FPathFindingResult PathResult = NavSystem->FindPathSync(Query);

    if (PathResult.IsSuccessful() && PathResult.Path.IsValid())
    {
        // 경로 포인트 순회
        for (const FNavPathPoint& PathPoint : PathResult.Path->GetPathPoints())
        {
            // PathPoint.Location — 각 웨이포인트 위치
        }
    }
}

6.2 커스텀 웨이포인트 시스템 — BFS 활용

NavMesh를 사용하지 않는 단순한 웨이포인트 기반 이동에서는 직접 BFS/Dijkstra를 구현할 수 있습니다.

WaypointSubsystem.h

UCLASS()
class UWaypointSubsystem : public UWorldSubsystem
{
    GENERATED_BODY()

public:
    // 웨이포인트 그래프 등록
    void RegisterWaypoint(int32 WaypointId, const FVector& Location);
    void ConnectWaypoints(int32 FromId, int32 ToId, float Cost = 1.0f);

    // BFS — 가중치 없는 최단 경로 탐색
    TArray<int32> FindShortestPathBFS(int32 StartId, int32 GoalId) const;

    // 다익스트라 — 가중치 기반 최단 경로 탐색
    TArray<int32> FindShortestPathDijkstra(int32 StartId, int32 GoalId) const;

private:
    TMap<int32, FVector> WaypointLocations;
    TMap<int32, TArray<TPair<int32, float>>> AdjacencyList; // {이웃 ID, 비용}
};

WaypointSubsystem.cpp

TArray<int32> UWaypointSubsystem::FindShortestPathBFS(int32 StartId, int32 GoalId) const
{
    if (!AdjacencyList.Contains(StartId) || !AdjacencyList.Contains(GoalId))
    {
        return {};
    }

    TMap<int32, int32> PreviousNode;
    TQueue<int32> Queue;

    PreviousNode.Add(StartId, -1);
    Queue.Enqueue(StartId);

    while (!Queue.IsEmpty())
    {
        int32 Current;
        Queue.Dequeue(Current);

        if (Current == GoalId)
        {
            break;
        }

        const TArray<TPair<int32, float>>* Neighbors = AdjacencyList.Find(Current);
        if (!Neighbors)
        {
            continue;
        }

        for (const TPair<int32, float>& Edge : *Neighbors)
        {
            int32 NeighborId = Edge.Key;
            if (!PreviousNode.Contains(NeighborId))
            {
                PreviousNode.Add(NeighborId, Current);
                Queue.Enqueue(NeighborId);
            }
        }
    }

    // 경로 복원
    TArray<int32> Path;
    if (!PreviousNode.Contains(GoalId))
    {
        return {}; // 경로 없음
    }

    for (int32 Vertex = GoalId; Vertex != -1; Vertex = PreviousNode[Vertex])
    {
        Path.Add(Vertex);
    }
    Algo::Reverse(Path);
    return Path;
}

6.3 퀘스트 의존성 그래프 — DFS 위상 정렬

퀘스트 간 선행 조건(A 퀘스트를 완료해야 B 퀘스트 해금)을 방향 그래프로 모델링하고, DFS 위상 정렬로 완료 가능한 퀘스트 순서를 계산합니다.

// 퀘스트 의존성 관리자
UCLASS()
class UQuestDependencyManager : public UObject
{
    GENERATED_BODY()

public:
    // 퀘스트 A가 완료되어야 퀘스트 B를 시작 가능
    void AddDependency(FName PrerequisiteQuestId, FName DependentQuestId);

    // 사이클 없이 수행 가능한 퀘스트 순서 반환 (위상 정렬)
    TArray<FName> GetCompletionOrder() const;

    // 선행 퀘스트가 모두 완료되었는지 확인
    bool CanStartQuest(FName QuestId, const TSet<FName>& CompletedQuests) const;

private:
    TMap<FName, TArray<FName>> QuestGraph; // 선행 → 후행 퀘스트

    void TopologicalDFS(FName QuestId,
                        TSet<FName>& Visited,
                        TArray<FName>& Result) const;
};

bool UQuestDependencyManager::CanStartQuest(
    FName QuestId,
    const TSet<FName>& CompletedQuests) const
{
    // 이 퀘스트를 후행으로 갖는 모든 선행 퀘스트를 역방향으로 탐색
    for (const TTuple<FName, TArray<FName>>& Entry : QuestGraph)
    {
        if (Entry.Value.Contains(QuestId))
        {
            // QuestId의 선행 조건: Entry.Key
            if (!CompletedQuests.Contains(Entry.Key))
            {
                return false;
            }
        }
    }
    return true;
}

6.4 AI 행동 그래프 — 상태 전이

AI의 상태(순찰 → 추격 → 공격 → 복귀)를 방향 그래프로 표현하고, 조건을 간선 가중치로 활용합니다.

// EAIState 각 정점, 전이 조건을 간선으로 표현하는 AI 상태 그래프
UENUM(BlueprintType)
enum class EAIState : uint8
{
    Patrol     UMETA(DisplayName = "Patrol"),
    Chase      UMETA(DisplayName = "Chase"),
    Attack     UMETA(DisplayName = "Attack"),
    Retreat    UMETA(DisplayName = "Retreat"),
};

// BFS로 현재 상태에서 목표 상태까지 도달 가능한지 확인
bool CanTransitionTo(EAIState CurrentState, EAIState TargetState,
                     const TMap<EAIState, TArray<EAIState>>& TransitionGraph)
{
    if (CurrentState == TargetState)
    {
        return true;
    }

    TSet<EAIState> Visited;
    TQueue<EAIState> Queue;
    Queue.Enqueue(CurrentState);
    Visited.Add(CurrentState);

    while (!Queue.IsEmpty())
    {
        EAIState Current;
        Queue.Dequeue(Current);

        const TArray<EAIState>* Neighbors = TransitionGraph.Find(Current);
        if (!Neighbors)
        {
            continue;
        }

        for (EAIState Next : *Neighbors)
        {
            if (Next == TargetState)
            {
                return true;
            }
            if (!Visited.Contains(Next))
            {
                Visited.Add(Next);
                Queue.Enqueue(Next);
            }
        }
    }

    return false;
}

---

핵심 요약

항목	BFS	DFS	다익스트라
자료구조	std::queue / TQueue	std::stack / 재귀	std::priority_queue / min-heap
시간 복잡도	O(V+E)	O(V+E)	O((V+E) log V)
가중치 처리	X	X	O (양수 가중치)
최단 경로	O (무가중치)	X	O (가중치)
주요 활용	연결 요소, 최단 홉 수	사이클 감지, 위상 정렬	NavMesh, 웨이포인트
UE5 연관 API	TQueue, TSet	TArray + 재귀	UNavigationSystemV1

그래프와 BFS/DFS는 단순한 이론 지식이 아니라, Unreal Engine의 AI 시스템과 직접 맞닿아 있는 실전 알고리즘입니다. UNavigationSystemV1이 내부적으로 수행하는 경로탐색의 원리를 이해하고, 필요한 경우 커스텀 웨이포인트 시스템이나 퀘스트 의존성 그래프를 직접 구현할 수 있어야 진정한 Unreal Engine C++ 개발자라고 할 수 있습니다.