Prim 알고리즘을 이용한 맵 생성

📌 1. Prim 알고리즘 개요

Prim 알고리즘은 하나의 정점을 시작으로 최소 비용 간선을 하나씩 선택해 트리 형태로 확장해가는 방식의 최소 스패닝 트리(MST) 알고리즘이다.

• 트리 중심 접근 방식
• 정점 집합에 인접한 간선 중 가장 적은 비용을 가진 간선을 선택하여 확장
• Kruskal과 차이점:
  • Kruskal: 간선 중심 탐색
  • Prim: 정점 집합 중심 확장

---

🌟 2. 알고리즘 특징

항목	Prim	Kruskal
기준	현재 트리 내 정점들	전체 간선 목록
사이클 방지	정점 방문 여부로 판단	Disjoint Set 사용
자료구조	우선순위 큐	간선 리스트, Disjoint Set

💡 다익스트라와 유사하지만 기준점이 다르다:

• 다익스트라: 고정된 시작점 기준 최단 거리 계산
• Prim: 트리 내부 모든 정점을 기준으로 확장

---

🧱 3. 미로 맵 생성 흐름 요약

1. 맵은 격자 기반으로 구성되며 홀수 좌표에 정점(EMPTY), 짝수 좌표에 벽(WALL)을 배치.
2. 각 정점에서 우측/하단 연결 후보 간선을 생성.
3. 간선마다 랜덤한 비용(cost) 부여 → 미로의 랜덤성 확보
4. Prim 알고리즘을 이용해 최소 비용 간선부터 순차적으로 선택, 경로를 뚫어 미로 생성.

---

🛠 4. 구현 상세 분석

---

📌 4.1 맵 초기화 (격자 형태 구성)

for (int32 y = 0; y < _size; y++) {
    for (int32 x = 0; x < _size; x++) {
        _tile[y][x] = (x % 2 == 0 || y % 2 == 0) ? TileType::WALL : TileType::EMPTY;
    }
}

• 짝수 좌표는 벽, 홀수 좌표는 정점
• 완전한 격자 형태로 시작

---

📌 4.2 간선 후보 등록

map<Pos, vector<CostEdge>> edges;

for (int32 y = 0; y < _size; y++) {
    for (int32 x = 0; x < _size; x++) {
        if (x % 2 == 0 || y % 2 == 0) continue;

        Pos u = Pos{ y, x };

        if (x < _size - 2) {
            Pos v = Pos{ y, x + 2 };
            int cost = rand() % 100;
            edges[u].push_back({ cost, v });
            edges[v].push_back({ cost, u });
        }

        if (y < _size - 2) {
            Pos v = Pos{ y + 2, x };
            int cost = rand() % 100;
            edges[u].push_back({ cost, v });
            edges[v].push_back({ cost, u });
        }
    }
}

• 우측/하단으로 이동 가능한 간선을 생성
• 간선 비용을 랜덤으로 부여
• edges는 인접 리스트 형태로 간선 정보를 저장

---

📌 4.3 Prim 알고리즘 본격 실행

priority_queue<CostEdge> pq;
map<Pos, bool> added;
map<Pos, Pos> parent;
map<Pos, int32> best;

for (int32 y = 0; y < _size; y++)
    for (int32 x = 0; x < _size; x++) {
        Pos p = { y, x };
        best[p] = INT32_MAX;
        added[p] = false;
    }

Pos start = { 1, 1 };
pq.push({ 0, start });
best[start] = 0;
parent[start] = start;

while (!pq.empty()) {
    CostEdge edge = pq.top();
    pq.pop();
    Pos v = edge.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 (auto& e : edges[v]) {
        if (added[e.vtx]) continue;
        if (e.cost > best[e.vtx]) continue;

        best[e.vtx] = e.cost;
        parent[e.vtx] = v;
        pq.push(e);
    }
}

• 우선순위 큐를 이용해 현재 트리에 가장 적은 비용으로 연결 가능한 간선을 선택
• 방문된 정점인지(added) 체크하여 중복 제거
• 정점 간의 중간 좌표를 계산하여 통로를 뚫음

---