다리만들기2

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
struct PAIR {
    int x, y;
    PAIR(int x, int y) {
        this->x = x;
        this->y = y;
    }
};
 
int h, w;
int map[11][11];
int real[11][11];
bool ck = false;
bool dos[11];
bool d[11][11];
int realmap[7][7];
bool findd = false;
int ans = 987654321;
int cnt = 1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
class Edge {
public:
    int node[2];
    int distance;
    Edge(int a, int b, int distance) {
        this->distance = distance;
        this->node[0] = a;
        this->node[1] = b;
    }
    bool operator < (Edge& edge) {
        return this->distance < edge.distance;
    }
};
vector<Edge> v;
void bfs(int x, int y, int ct) {
    queue<PAIR> q;
    q.push(PAIR(x, y));
    d[x][y] = true;
    real[x][y] = ct;
    while (!q.empty()) {
        x = q.front().x;  y = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx >= 1 && nx <= h && ny >= 1 && ny <= w) {
                if (d[nx][ny] == false && map[nx][ny] == 1) {
                    d[nx][ny] = true;
                    real[nx][ny] = ct;
                    q.push(PAIR(nx, ny));
                }
            }
        }
    }
}
bool check(int nx, int ny) {
    if (nx >= 1 && nx <= h && ny >= 1 && ny <= w) {
        return true;
    }
    return false;
}
void make_value(int x, int y, int ct, int idx) {
    int nx = x; int ny = y;
    int c = 0;
    while (true) {
        nx += dx[idx]; ny += dy[idx]; c++;
        if (check(nx, ny)) {
            if (real[nx][ny] == ct) {
                break;
            }
            else {
                if (real[nx][ny] != ct && real[nx][ny] != 0) {
                    if (c - 1 >= 2) {
                        if (realmap[ct][real[nx][ny]] == 0) {
                            realmap[ct][real[nx][ny]] = c - 1;
                            realmap[real[nx][ny]][ct] = c - 1;;
                            break;
                        }
                        if (realmap[ct][real[nx][ny]] > c - 1) {
                            realmap[ct][real[nx][ny]] = c - 1;
                            realmap[real[nx][ny]][ct] = c - 1;;
                            break;
                        }
                        else break;
                    }
                    else {
                        break;
                    }
                }
            }
        }
        else break;
    }
}
 
bool chek() {
    for (int i = 1; i < cnt; i++) {
        if (dos[i] == false) {
            return false;
        }
    }
    return true;
}
void bfs2(int idx) {
    ck = false;
    findd = false;
    queue<int> q;
    q.push(idx);
    dos[idx] = true;
    int ct = 0;;
    while (!q.empty()) {
        idx = q.front();
        //cout << idx << endl;
        q.pop();
        for (int i = 1; i < cnt; i++) {
            if (dos[i] == false && realmap[idx][i] != 0) {
                dos[i] = true;
                q.push(i);
            }
        }
    }
    for (int i = 1; i < cnt; i++) {
        if (dos[i] == false) {
            ck = true;
        }
    }
    if (ck == false && ans > ct) {
        ans = ct;
        findd = true;
    }
}
int getParent(int parent[], int a) {
    if (parent[a] == a) return a;//종료구문
    return parent[a] = getParent(parent, parent[a]);
}
//부모노드 합치기
void unionParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
//같은 부모를 가지는지 확인하기
int findParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    else return 0;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> map[i][j];
        }
    }
        for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++) {
            if (d[i][j] == false && map[i][j] == 1) {
                bfs(i, j, cnt);
                cnt++;
            }
        }
    }
 
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (real[i][j] != 0) {
                for (int k = 0; k < 4; k++) {
                    make_value(i, j, real[i][j], k);
                }
            }
        }
    }
    for (int i = 1; i < cnt; i++) {
        bfs2(i);
        memset(dos, false, sizeof(dos));
    }
    if (ans == 987654321) {
        cout << -1 << '\n';
        return 0;
    }
    for (int i = 1; i < cnt; i++) {
        for (int j = i + 1; j < cnt; j++) {
            if (realmap[i][j] != 0) {
                v.push_back(Edge(i, j, realmap[i][j]));
            }
        }
    }
    //cout<<v.size()<<'\n';
        sort(v.begin(), v.end());
    /*for (int i = 0; i < v.size(); i++) {
        cout << v[i].node[0] << ' ' << v[i].node[1] << ' ' << v[i].distance << '\n';
    }*/
    bool check[11]; memset(check, false, sizeof(check));
    for (int i = 0; i < v.size(); i++) {
        check[v[i].node[0]] = true;
        check[v[i].node[1]] = true;
    }
        int parent[11];
    for (int i = 0; i < cnt; i++) {
        parent[i] = i;
    }
    int sum = 0;
 
    for (int i = 0; i < v.size(); i++) {
        if (!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1)) {
            sum += v[i].distance;
                unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
        }
    }
    cout << sum << '\n';
        return 0;
}

MST 알고리즘을 이용한 문제였다.

단순하게 BFS나 DFS로는 풀어내기힘든문제,

최소한의 비용으로 모든걸연결하는게 목표이므로, 그냥 연결만하는게 아니라 비용에 따른 가치도 따져야한다

그래서 반드시 MST가필요하다고 생각했고, 맵 탐색을 통해 섬 영역을 나누고 그나눠진영역을 토대로 가장짧은 다리길이를 구해서 vector에 저장하고 그것을 정렬한 뒤  MST알고리즘을 적용하면끝난다.