최소 신장 트리

최소 신장 트리

• 신장 트리란 그래프에서 모든 정점을 포함하고 정점 간 서로 연결이 되며 싸이클이 존재하지 않는 그래프를 의미한다.

• 최소 신장 트리란 그래프의 신장 트리들 중 간선의 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 한다.

• ex) 도시를 모두 연결하는 루트를 구성하라. 단 도로의 길이를 최소로 하라.

• 최소 신장 트리를 구하는 알고리즘은 대표적으로 Kruskal알고리즘과 Prim알고리즘이 있다.

Kruskal Algorithm

• Kruskal 알고리즘은 그래프 간선들을 오름차순으로 정렬을 한 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다.

• 여기서 사이클 판단은 Union-Find 자료구조( DisJointSet 서로소 집합을 표현하는 자료구조)를 사용한다.

Union-Find(DisJointSet)

• Union-Find(DisJointSet)

  • 서로 다른 root를 가진 subtree에 대하여 하나의 root의 subtree로 Union(합치기)하는 알고리즘이다.

  • 이 자료구조를 사용하면 서로 다른 subtree들의 합병을 빠르게 할 수 있고, 특정 node의 root를 찾는 연산이 수월하다.

  • 트리의 높이와 시간복잡도가 같다 (최악 O(N-1))

class DisJointSet
{
public:
	DisJointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0;i < n;i++)
			_parent[i] = i;
	}

	// 리더를 찾는다.
	int Find(int u)
	{
		if (u == _parent[u])
			return u;
		return _parent[u] = Find(_parent[u]);
	}

	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[v] == _rank[v])
			_rank[v]++;

	}
private:
	vector<int> _parent;
	vector<int> _rank;
};

• Kruskal 알고리즘은 DisJointSet을 사용하여 사이클의 발생 여부를 검사하게 된다.
• 만약 한 정점과 다른 정점으로의 간선이 현재 가장 최소 가중치를 가진 간선이라면 두 정점사이의 간선을 최종 루트에 추가하기 위해 사이클을 검사하게 된다.
• 이 때 각 정점들의 root를 찾아 서로 다르다면 각각의 집합으로 판단하여 union하고 root가 같다면 이미 같은 집합 내부에 있는 것이므로 사이클이 발생한다고 판단하여 간선을 제외하게 된다.

// Kruskal Algorithm을 사용한 맵 만들기 함수
void Board::GenerateMap_Kruskal() 
{

    struct CostEdge
    {
        int cost;
        Pos u;
        Pos v;

        bool operator<(CostEdge& other)
        {
            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;
        }
    }

    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;
    }
}

Prim Algorithm

• Kruskal과는 다르게 시작정점이 주어져, 시작정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다.
• 가장 첫 단계에서는 시작 정점만이 최소 신장 트리 집합에 포함된 상태로 시작한다.
• 이후 앞 단계에서 만들어진 최소 신장 트리에 인접한 정점들을 조사하여 가장 최소의 비용을 가진 간선과 연결된 정점을 선택하여 트리를 확장한다.(priority_queue를 사용)
• 위 과정을 트리가 (N-1)개의 간선을 가질 때 까지 반복한다.

// Prim Algorithm을 사용한 맵 만들기 함수
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
    // - Prim은 연재 트리가 기준인 간선의 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);
        }
    }
}