백준 18769번: 그리드 네트워크 (C++)

https://www.acmicpc.net/problem/18769

18769번: 그리드 네트워크

---

Solved By: MST, Implementation

 

간단한 MST 문제였지만 좌표를 어떻게 모델링하여 코드를 짤지는 조금 어려웠습니다.

예를 들어 2행 3열의 네트워크가 있으면 5번 노드를 나타낼 때, (i - 1) * c + j (5번 노드는 2행 2열)과 같이 나타내려 했는데 행간과 열간의 가중치를 할당하기 어려웠습니다.

 

그래서, 직관적으로 구현을 하였습니다. (보기 흉한 코드이지만..)

좌표를 pair<int, int>로 잡고, parent는 2차원으로 선언하여 row칸에는 first, col칸에는 second를 할당하여 MST를 구했습니다.

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#define pii pair<int, int>
#define MAX 501
using namespace std;

int T;
vector<pair<pair<pii, pii>, int>> edges;
pii parent[MAX][MAX];

bool cmp(pair<pair<pii, pii>, int> a, pair<pair<pii, pii>, int> b){
    return a.second < b.second;
}

pii getRoot(pii node){
    if(node == parent[node.first][node.second]) return node;
    return parent[node.first][node.second] = getRoot(parent[node.first][node.second]);
}

bool find(pii a, pii b){
    pii ga = getRoot(a);
    pii gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(pii a, pii b){
    pii ga = getRoot(a);
    pii gb = getRoot(b);
    
    if(ga < gb) parent[gb.first][gb.second] = ga;
    else parent[ga.first][ga.second] = gb;
}

int main(){
    cin >> T;
    vector<int> res;
    for(int t = 0; t < T; t++){
        int r, c; cin >> r >> c;
        
        edges.clear();
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                parent[i][j] = {i, j};
            }
        }
        
        for(int i = 1; i <= r; i++){
            for(int j = 1; j < c; j++){
                int w; cin >> w;
                edges.push_back({{{i, j}, {i, j + 1}}, w});
            }
        }
        
        for(int i = 1; i < r; i++){
            for(int j = 1; j <= c; j++){
                int w; cin >> w;
                edges.push_back({{{i, j}, {i + 1, j}}, w});
            }
        }
        
        sort(edges.begin(), edges.end(), cmp);
        
        int result = 0;
        for(int i = 0; i < edges.size(); i++){
            pii first = edges[i].first.first;
            pii second = edges[i].first.second;
            if(find(first, second)){
                result += edges[i].second;
                unionNodes(first, second);
            }
        }
        
        res.push_back(result);
    }
    
    for(int i = 0; i < res.size(); i++) cout << res[i] << '\n';
    
    return 0;
}