[c++] 17472 - 다리만들기2 [BFS][크루스칼 알고리즘]

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

17472번: 다리 만들기 2

 

다리의 최단거리를 구해보는 문제이다.

 

문제를 보면 우선 다리의 조건은

 

1. 길이 2이상
2. 직선으로만 가야함

이다.

 

문제의 전체적인 풀이는 다음과 같다.

1. 구역을 나눠줌
2. 구역별로의 거리를 구함
3. 모든 구역을 연결하는 최소 길이를 찾음.

1, 2는 BFS를 사용해서 구한다.

3.은 프림알고리즘 혹은 크루스칼 알고리즘을 이용한다.

 

간선이 많지는 않은거같아 그냥 크루스칼을 사용했다.

 

단, 주의할점이

if(answer == 0 || plus != num-1){cout<<"-1";}

 

마지막 이 코드이다.

모두 연결되려면 선분의 개수가 구역개수 -1이어야 한다.

그렇지 않으면 모두 연결되지 않는다.

 

 

 

이 문제는 BFS를 쓸 수 있냐, 크루스칼 알고리즘을 적용할 생각을 할 수 있냐 그거인것 같다.

---

#include <bits/stdc++.h>
using namespace std;
#define MAX  999
int arr[10][10];
struct po{int x;int y;};
struct graph{int from;int to;int val;};
vector<vector<int>> road;
int  num=2;
int parent[50];

int getParent(int son){
    if(parent[son] == son) return son;
    else return getParent(parent[son]);
}    

int main(){
    int N,M; cin>>N>>M;
    int x[4] = {-1,0,1,0} , y[4] = {0,1,0,-1} ,xx,yy,xxx,yyy,temp;
    int answer = 0,start,end,plus = 0;
    for (int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>arr[i][j];}}
    queue<po> wait;
    //여기서부터 구역을 나눠주는 BFS
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(arr[i][j]==1){   
                wait.push({i,j});
                while(!wait.empty()){
                    xx = wait.front().x, yy=wait.front().y; wait.pop();
                    arr[xx][yy] = num;
                    for(int k=0;k<4;k++){
                        xxx= xx+x[k] , yyy=yy+y[k];
                        if(xxx>=0 && yyy>=0 && xxx<N && yyy<M){
                            if(arr[xxx][yyy]==1){wait.push({xxx,yyy});}
                        }
                    }
                }
                num+=1;
            }
        }
    }
    //여기서부터 구역끼리의 길이를 구해주는 과정
    for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(arr[i][j]>1) arr[i][j]--;}}
    num -= 2;
    for(int i=1;i<=num;i++){parent[i] = i;}
    road.resize(num+1,vector<int>(num+1,MAX));
    pair<int,int> direct[4] = {{-1,0},{0,1},{1,0},{0,-1}};
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(arr[i][j] != 0){
                for(int k=0;k<4;k++){
                    temp = 0, xx = i+direct[k].first, yy= j+direct[k].second;
                    while(xx>=0 && xx<N && yy>=0 && yy<M && arr[xx][yy]==0){
                        xx += direct[k].first , yy += direct[k].second , temp++; 
                    }
                    if(xx>=0 && xx<N && yy>=0 && yy<M && arr[xx][yy]>0 && arr[xx][yy] != arr[i][j] && temp>=2){
                        road[arr[i][j]][arr[xx][yy]] = min(road[arr[i][j]][arr[xx][yy]] , temp);
                    }
                }
            }
        }
    }
    //경로 저장
    vector<graph> roads;
    for(int i=1;i<=num;i++){
        for(int j=1;j<i;j++){
            if(road[i][j]!=MAX){
                roads.push_back({j,i,road[i][j]});
            }
        }
    }
    //크루스칼 알고리즘
    sort(roads.begin(),roads.end(),[](graph &a, graph &b){return a.val<=b.val;});
    for(auto K: roads){
        if(plus == num-1){break;}
        start = getParent(K.from);
        end = getParent(K.to);
        if(start != end){
            answer += K.val;
            parent[end] = start;
            plus++;
        }
    }
    if(answer == 0 || plus != num-1){cout<<"-1";}
    else cout<<answer<<endl;
}