[알고리즘] 프림 알고리즘(Prim Algorithm)을 이용한 길찾기

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

프림 알고리즘(Prim Algorithm)

그래프에서 최소 신장 트리를 만들어내는 알고리즘이다.

 

프림 알고리즘 생성 과정

1. 노드가 하나도 없는 최소 신장 트리를 준비한다.
2. 그래프에서 임의의 정점을 시작 정점으로 선택한 후 최소 신장 트리의 뿌리 노드로 삽입한다.
3. 간선의 가중치를 조사한다. 가중치가 작은 간선들을 골라 이 간선에 연결된 인접 정점을 최소 신장 트리에 삽입한다. 새로 삽입되는 정점은 기존 노드와 사이클을 형성하면 안 된다.
4. 최소 신장 트리가 그래프의 모든 정점을 연결할 때까지 3번 과정을 반복한다.

 

다익스트라(Dijkstra)와 프림(Prim) 알고리즘 차이

• 거의 유사하다. 차이점은 아래와 같다.
• 다익스트라(Dijkstra): '시작점'을 기준으로 최단거리 비용 검사
• 프림(Prim) : '현재 트리(정점 집합)'를 기준으로 간선 비용 검사

 

 

---

프림 알고리즘(Prim Algorithm)을 이용한 길찾기

본문내용넣기

 

 

 

---

 

프림 알고리즘을 이용한 길찾기 코드

 

Board.cpp

void Board::GenerateMap_Prim()
{
    struct CostEdge
    {
        int cost;
        Pos vtx;
 
        bool operator<(const CostEdge& other) const
        {
            return cost < other.cost;
        }
    };
 
    for (int32 y = 0; y < _size; y++)
    {
        for (int32 x = 0; x < _size; x++)
        {
            if (x % 2 == 0 || y % 2 == 0)
                _tile[y][x] = TileType::WALL;
            else
                _tile[y][x] = TileType::EMPTY;
        }
    }
 
    // edges[u] : u 정점과 연결된 간선 목록
    map<Pos, vector<CostEdge>> edges;
 
    // edges 후보를 랜덤으로 등록한다
    for (int32 y = 0; y < _size; y++)
    {
        for (int32 x = 0; x < _size; x++)
        {
            if (x % 2 == 0 || y % 2 == 0)
                continue;
 
            // 우측 연결하는 간선 후보
            if (x < _size - 2)
            {
                const int32 randValue = ::rand() % 100;
                Pos u = Pos{ y, x };
                Pos v = Pos{ y, x + 2};
                edges[u].push_back(CostEdge{ randValue, v });
                edges[v].push_back(CostEdge{ randValue, u });
            }
 
            // 아래로 연결하는 간선 후보
            if (y < _size - 2)
            {
                const int32 randValue = ::rand() % 100;
                Pos u = Pos{ y, x };
                Pos v = Pos{ y + 2, x };
                edges[u].push_back(CostEdge{ randValue, v });
                edges[v].push_back(CostEdge{ randValue, u });
            }
        }
    }
 
    // 해당 정점이 트리에 포함되어 있나?
    map<Pos, bool> added;
    // 어떤 정점이 누구에 의해 연결 되었는지
    map<Pos, Pos> parent;
    // 만들고 있는 트리에 인접한 간선 중, 해당 정점에 닿는 최소 간선의 정보
    map<Pos, int32> best;
 
    // 다익스트라랑 거의 유사함. 단,
    // - 다익스트라에서는 best가 [시작점]을 기준으로 한 cost
    // - 프람에서는 best가 [현재 트리]를 기준으로 한 간선 cost
 
    for (int32 y = 0; y < _size; y++)
    {
        for (int32 x = 0; x < _size; x++)
        {
            best[Pos{ y, x }] = INT32_MAX;
            added[Pos{ y, x }] = false;
        }
    }
 
    priority_queue<CostEdge> pq;
    const Pos startPos = Pos{ 1, 1 }; // 랜덤으로 정해도 됨
    pq.push(CostEdge{ 0, startPos });
    best[startPos] = 0;
    parent[startPos] = startPos;
 
    while (pq.empty() == false)
    {
        CostEdge bestEdge = pq.top();
        pq.pop();
 
        // 새로 연결된 정점
        Pos v = bestEdge.vtx;
        // 이미 추가되었다면 스킵
        if (added[v])
            continue;
 
        added[v] = true;
 
        // 맵에 적용
        {
            int y = (parent[v].y + v.y) / 2;
            int x = (parent[v].x + v.x) / 2;
            _tile[y][x] = TileType::EMPTY;
        }
 
        // 방금 추가한 정점에 인접한 간선들을 검사한다
        for (CostEdge& edge : edges[v])
        {
            // 이미 추가 되었으면 스킵
            if (added[edge.vtx])
                continue;
            // 다른 경로로 더 좋은 후보가 발견 되었으면 스킵
            if (edge.cost > best[edge.vtx])
                continue;
 
            best[edge.vtx] = edge.cost;
            parent[edge.vtx] = v;
            pq.push(edge);
        }
    }
}

 

---

 

실행파일