[백준 17472] 다리 만들기2

분류 

bfs, 크루스칼

 

요구사항

다리를 만들어서 섬들을 연결 할 때, 최소한의 수로 모든 섬 연결하기

-> 모든 노드를 연결하되, 최소로 연결하기 -> 최소스패닝트리

풀이

1. 각 섬에 번호 넣기

2. 섬에서 섬으로 연결되는 다리 숫자구하기

3. 다리 숫자 별 정렬

4. Union-Find

 

#include <stdio.h>
//#include <map>
#include <algorithm>
//#include "Windows.h"
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct go{
    int x;
    int y;
    int dist;
};
int n,m;
int ccnt=0;
int map[11][11];
int visit[11][11];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1};
int parent[10];
queue<go> pos_q[7];
vector<go> v;
void bfs(int r, int c, int num){
    queue<go> q;
    visit[r][c]=1;
    map[r][c]=num;
    pos_q[num].push({r,c});
    q.push({r,c});
    while(!q.empty()){
        int x = q.front().x;
        int y =q.front().y;
        q.pop();
        for(int i=0 ; i < 4 ; i++){
            int nr = x+dr[i];
            int nc = y+dc[i];
            if(map[nr][nc]==1 && visit[nr][nc]==0){
                visit[nr][nc]=1;
                map[nr][nc]=num;
                q.push({nr,nc});
                pos_q[num].push({r,c});
            }
        }
    }
}
void Get_dist(int r, int c , int now, int dir){
    int dist=0;
    int sr=r;
    int sc=c;
    while(true){
        int nr = r+dr[dir];
        int nc = c+dc[dir];
        //cout<<"nr"<<nr<<" "<<nc<<" "<<now<<endl;
        if(nr<0 || nc<0 || nr>=n || nc>=m) return;
        if(map[nr][nc]==now) {
            return;
        }
        if(map[nr][nc]==0){
            dist++;
            r=nr;
            c=nc;
       //     cout<<"B"<<endl;
        }
        //다른 섬을 만났다.
        if(map[nr][nc] != 0 && map[nr][nc] !=now){
            v.push_back({map[sr][sc], map[nr][nc], dist});
            return;
        }
    }
}
bool cmp(go a, go b){
    if(a.dist< b.dist) return true;
    return false;
}
int Find(int x){
    if(parent[x]==x) return x;
    else return x=Find(parent[x]);
}
void Union(int x, int y){
    x=Find(x);
    y= Find(y);
    if(x!=y){
        parent[x]=y;
    }

}
int main(){
    int island=0;
    int island_cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1; i <= 10;i++) parent[i]=i;
    for(int i=0 ; i <n ; i++){
        for(int j=0; j<m ; j++){
            scanf("%d",&map[i][j]);
        }
    }

    //bfs로 영역 정하기
    for(int i=0 ; i <n ; i++){
        for(int j=0; j<m ; j++){
            if(map[i][j]==1 && visit[i][j]==0){
                island_cnt++;
                bfs(i,j,++island);
            }
        }
    }
    //각 섬까지의 거리 구하기
    memset(visit,0,sizeof(visit));
    for(int i=0 ; i <n ; i++){
        for(int j=0; j<m ; j++){
            if(map[i][j]!=0 && visit[i][j]==0){
                visit[i][j]=1;
                for(int k=0 ; k<4; k++){
                    Get_dist(i,j,map[i][j],k);    
                }
            }
        }
    }
    //섬 정렬
    int vertex=0;
    int flag=0;
    int ans=0;
    sort(v.begin(),v.end(), cmp);
    for(int i=0 ; i < v.size() ; i++){
        if(v[i].dist==1) continue;
        if(Find(v[i].x) != Find(v[i].y)){
            Union(v[i].x,v[i].y);
            ans+=v[i].dist;
            vertex++;
        }
        if(vertex==island_cnt-1){
            flag=1;
            break;
        }
    }
    if(flag==1){
        cout<<ans<<endl;
    }
    else{
        cout<<-1<<endl;
    }
    
    
}