[BOJ 17427] 다리 만들기 (C++)

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

17472번: 다리 만들기 2

 

#include <bits/stdc++.h>

using namespace std;
int graph[11][11];
bool visited[11][11];
int parents[7];
int N, M;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};

class Node{
    public:
        int start;
        int end;
        int cost;
        Node(int start, int end, int cost){
            this->start=start;
            this->end=end;
            this->cost=cost;
        }
};

struct compare{
    bool operator()(Node a, Node b){
        return a.cost>b.cost;
    }
};

priority_queue<Node, vector<Node>, compare> pq;

bool isPossible(int y, int x){
    if (y<0 || x<0 || y>=N || x>=M){
        return false;
    }
    else{
        return true;
    }
}

void findBridge(int start,int y, int x, int dy, int dx){
    int cnt=1;
    int num=0;
    while (isPossible(y+dy, x+dx) && graph[y+dy][x+dx]==0){     //벽을 만나거나 1을 만나면 나가리
        cnt++;
        //num=graph[y+dy][x+dx];
        y+=dy;
        x+=dx;
    }
    if (isPossible(y+dy, x+dx) && graph[y+dy][x+dx]!=0 && cnt>=2){
        num=graph[y+dy][x+dx];
        pq.push(Node(start,num,cnt));
    }
}

void bfs(int y, int x, int num){
    queue<pair<int,int> > q;
    q.push(make_pair(y,x));
    graph[y][x]=num;
    visited[y][x]=true;
    while (!q.empty()){
        int row=q.front().first;
        int col=q.front().second;
        q.pop();
        for (int i=0; i<4; i++){
            int nrow=row+dy[i];
            int ncol=col+dx[i];
            if (isPossible(nrow,ncol) && graph[nrow][ncol]==1){
                if (!visited[nrow][ncol]){
                    q.push(make_pair(nrow,ncol));
                    graph[nrow][ncol]=num;
                    visited[nrow][ncol]=true;
                }
            }
        }
    }
}

int find(int x){
    if (parents[x]==x){
        return x;
    }
    return parents[x]=find(parents[x]);
}

void union_(int a, int b){
    int pa=find(a);
    int pb=find(b);
    if (pa!=pb){
        parents[pa]=pb;
    }
}

int main(){
    int x;
    cin>>N>>M;
    vector<pair<int,int> > ones;
    int num=1;      //섬의 개수
    int ans=0;
    int cnt=0;
    for (int i=0; i<7; i++){
        parents[i]=i;
    }
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            cin>>x;
            graph[i][j]=x;
            visited[i][j]=false;
            if (x==1){
                ones.push_back(make_pair(i,j));
            }
        }
    }
    for (int i=0; i<ones.size(); i++){
        int y=ones[i].first;
        int x=ones[i].second;
        if (!visited[y][x]){
            bfs(y,x,num);
            num++;
        }
    }
    num-=1;
    for (int i=0; i<ones.size(); i++){
        int y=ones[i].first;
        int x=ones[i].second;
        int start=graph[y][x];
        for (int j=0; j<4; j++){
            int ny=y+dy[j];
            int nx=x+dx[j];
            if (isPossible(ny,nx) && graph[ny][nx]==0){
                findBridge(start,ny,nx,dy[j],dx[j]);
            }
        }
    }
    while (!pq.empty()){
        Node now=pq.top();
        pq.pop();
        int nowstart=now.start;
        int nowend=now.end;
        if (find(nowstart)!=find(nowend)){
            union_(nowstart,nowend);
            cnt++;
            ans+=now.cost;
        }
        if (cnt==num-1){
            break;
        }
    }
    if (cnt<num-1){             //모두 잇는 경우가 없을때!!(이 조건 중요)
        ans=-1;
    }
    cout<<ans<<"\n";  
    return 0;
}

모두 잇는 경우가 없을 때 판정하는 조건문이 필수였다.