[C++로 풀이] 지형 이동 (MST, BFS) ⭐⭐⭐⭐

📌 지형 이동

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

• 1️⃣ BFS 를 통해 연결 되어 있는 그래프(= 사다리 안놓고 갈 수 있는 곳)들로 구분한다.
• 2️⃣ 각 그래프를 연결 하는 비용(= 사다리 비용)을 구한다.
• 3️⃣ BFS 로 나눈 그래프들을 하나의 그래프로 통합할 수 있도록 사이클 없고 최소 비용(= 사다리 비용)으로 연결하는 최소 신장 트리를 만든다.

1️⃣ BFS 를 통해 연결 되어 있는 그래프(= 사다리 안놓고 갈 수 있는 곳)들을 구분한다.

graph_number 같은 값을 가진 그래프는 같은 그래프로 구분한다.

• graph_number 값이 0 이 아닌 곳은 이미 탐색이 완료 되었다는 곳이다.
• 그래픝 넘버가 같은 값인 위치들은 서로 같은 그래프이다.
  • 여기서 ‘같은 그래프’란 사다리 안 놓고 서로 한 번에 갈 수 있는 위치들.

2️⃣ 각 그래프를 연결 하는 사다리 비용(간선 가중치)을 구한다.

edges 에 두 그래프 사이를 연결하는 비용을 저장해둔다.

BFS 로 여러 그래프로 구분하는 작업을 모두 마친 후, 그래프 사이의 비용(= 사다리 비용)을 모두 구해 edges 에 저장한다.

3️⃣ 그래프들을 모두 최소 신장 트리로서 하나의 그래프로 통합하여 연결한다. (with 크루스칼 알고리즘)

(C++) 최소 신장 트리 MST, 크루스칼 알고리즘, 프림 알고리즘

• 최소 간선부터 차례 차례 검사하며 사이클이(= 부모, 즉 루트가 같지 않은) 없으면서 최소 가중치 간선만을 사용하여 그래프를 하나로 통합한다. 즉, 모두 연결함. 👉 최소 신장 트리
  • 최소 사다리 비용을 들여서 모든 위치를 다 갈 수 있게 연결하는 작업.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Pos { int i, j; }; // 위치 (BFS 에 사용)
struct Edge { int cost, graph_1, graph_2; }; // 간선 (edges 에 저장할 단위로 비용, 간선의 양 끝점 함께 묶어 저장)
bool cmp(const Edge& a, const Edge& b) { return a.cost < b.cost; } // 크루스칼은 가중치 별 오름차순 정렬이 필요하기 떄문에 비용으로 크기 따지는 비교 함수 마련

int graph_number[301][301] = { 0 };  // 위치 별로 속한 그래프를 구분
vector<Edge> edges; // 간선 정보들 저장
vector<int> parent; // 그래프 넘버별로 부모 정점 저장 (같은 부모면 같은 그래프)
int group_count = 0; // 현재까지 생긴 그래프 수 (넘버 저장)
int N = 0;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, -1, 1 };

vector<vector<int>> _land;
int _height;

void BFS(Pos start) {

    queue<Pos> q;
    q.push(start);
    // BFS 로 탐색할 수 있는, 사다리 안타고 갈 수 있는 연결된 하나의 그래프는 모두 graph_number[start.i][start.j] 로 통일되어 같은 그래프임을 표시할 것
    graph_number[start.i][start.j] = ++group_count;

    while (!q.empty()) {
        Pos now = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            Pos next{ now.i + dy[i], now.j + dx[i] };

            if (next.i < 0 || next.i >= N || next.j < 0 || next.j >= N) continue;
            if (graph_number[next.i][next.j] != 0) continue;
            // 사다리 비용 안쓰고 그냥 갈 수 있는 경우에만 예약 
            if (abs(_land[now.i][now.j] - _land[next.i][next.j]) <= _height) {
                graph_number[next.i][next.j] = group_count;
                q.push(next);
            }
        }
    }
}

// 크루스칼의 Find
int getParent(int a) {
    if (parent[a] == a) return a;
    return getParent(parent[a]);
}

// 크루스칼의 Union
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;

    N = land.size();
    _land = land;
    _height = height;

    // 1️⃣ BFS 로 사다리 안 쓰고 갈 수 있는 연결된 그래프들로 나누기. (같은 그래프끼린 같은 번호 부여)
    // graph_number
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (graph_number[i][j] == 0)
                BFS({ i, j });

    // 2️⃣ 각각의 그래프들끼리 연결할 수 있는 사다리 비용(간선 가중치) 저장 
    // edges
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < 4; ++k) {
                Pos next{ i + dy[k], j + dx[k] };

                if (next.i < 0 || next.i >= N || next.j < 0 || next.j >= N) continue;
                if (graph_number[i][j] == graph_number[next.i][next.j]) continue; // 같은 그래프면 사다리 놓을 필요 없음
                int cost = abs(_land[i][j] - _land[next.i][next.j]);
                edges.push_back({ cost, graph_number[i][j], graph_number[next.i][next.j] });
            }
        }
    }

    // 3️⃣ 크루스칼 알고리즘을 사용해 그래프들을 하나로 통합하는데 최소 신장 트리로서 통합한다. (최소의 사다리 비용을 들여서 사이클 없이)
    // 정렬 (최소 간선부터)
    sort(edges.begin(), edges.end(), cmp); 
    // 부모 초기화 (인덱스는 하나의 그래프에 대응)
    parent.resize(group_count + 1);
    for (int i = 1; i <= group_count; ++i)
        parent[i] = i;
    for (int i = 0; i < edges.size(); ++i) {
        if (getParent(edges[i].graph_1) != getParent(edges[i].graph_2)) { // 부모가 같지 않다면 (즉, 같은 그래프가 아니라면)
            answer += edges[i].cost;
            unionParent(edges[i].graph_1, edges[i].graph_2); // 통합한다.
        }
    }
    // MST 로 만듦으로서 하나의 그래프로 통합하였으니 이제 모든 그래프의 부모가 같게 된다.

    return answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기