[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)을 이용한 길찾기

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

 

목차

 

 

 

---

 

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

 

크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘을 이용한 길찾기 알고리즘 만들기.

---

DisjointSet.h 생성

DisjointSet.h를 새롭게 생성한다. 전에 사용한 DisjointSet 코드를 넣어준다.

 

#pragma once
class DisjointSet
{
public:
    DisjointSet(int n) : _parent(n), _rank(n, 1)
    {
        for (int i = 0; i < n; i++)
            _parent[i] = i;
    }
 
    // 조직 폭력배 구조?
    // [1]        [3]
    // [2]     [4][5][0]
 
    // 니 대장이 누구니?
    int Find(int u)
    {
        if (u == _parent[u])
            return u;
 
        //_parent[u] = Find(_parent[u]);
        //return _parent[u];
 
        return _parent[u] = Find(_parent[u]);
    }
    // u와 v를 합친다
    void Merge(int u, int v)
    {
        u = Find(u);
        v = Find(v);
 
        if (u == v)
            return;
 
        if (_rank[u] > _rank[v])
            swap(u, v);
 
        // rank[u] <= rank[v] 보장됨
        _parent[u] = v;
 
        if (_rank[u] == _rank[v])
            _rank[v]++;
    }
private:
    vector<int> _parent;
    vector<int> _rank;
};

---

 

Board.h & Board.cpp

 

Board.h

#pragma once
#include "ConsoleHelper.h"
 
class Player;
 
enum
{
    BOARD_MAX_SIZE = 100
};
 
enum class TileType
{
    NONE = 0,
    EMPTY,
    WALL,
};
 
struct CostEdge
{
    int cost;
    Pos u;
    Pos v;
 
    bool operator<(CostEdge& other)
    {
        return cost < other.cost;
    }
};
 
class Board
{
public:
    Board();
    ~Board();
 
    void            Init(int32 size, Player* player);
    void            Render();
 
    void            GenerateMap();
    TileType        GetTileType(Pos pos);
    ConsoleColor    GetTileColor(Pos pos);
 
    Pos                GetEnterPos() { return Pos{ 1, 1 }; }
    Pos                GetExitPos() { return Pos{ _size - 2, _size - 2 }; }
    int32            GetSize() { return _size; }
 
private:
    TileType        _tile[BOARD_MAX_SIZE][BOARD_MAX_SIZE] = {};
    int32            _size = 0;
    Player*            _player = nullptr;
};

struct CostEdge 생성

 

Board.cpp 수정된 부분

void Board::GenerateMap()
{
    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;
        }
    }
    
    vector<CostEdge> edges;
 
    // edges 후보를 랜덤 cost로 등록한다
    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;
                edges.push_back(CostEdge{ randValue, Pos{y, x}, Pos{y, x + 2 } });
            }
 
            // 아래로 연결하는 간선 후보
            if (y < _size - 2)
            {
                const int32 randValue = ::rand() % 100;
                edges.push_back(CostEdge{ randValue, Pos{y, x}, Pos{y + 2, x} });
            }
        }
    }
 
    std::sort(edges.begin(), edges.end());
 
    DisjointSet sets(_size * _size);
 
    for (CostEdge& edge : edges)
    {
        int u = edge.u.y * _size + edge.u.x;
        int v = edge.v.y * _size + edge.v.x;
        // 같은 그룹이면 스킵 (안 그러면 사이클 발생)
        if (sets.Find(u) == sets.Find(v))
            continue;
 
        // 두 그룹을 합친다
        sets.Merge(u, v);
 
        // 맵에 적용
        int y = (edge.u.y + edge.v.y) / 2;
        int x = (edge.u.x + edge.v.x) / 2;
        _tile[y][x] = TileType::EMPTY;
    }
}

 

vector<CostEdge> edges를 생성하여 크루스칼 알고리즘을 만든다.

 

---

 

실행파일

player.cpp 

DIR_COUNT = 4 로 수정하여, 대각선 이동은 불가능하도록 하였다.

 

 

 

 

 

---

 

마무리

마무리