[알고리즘] 백준 17472 - 다리 만들기 2 (C++)

[문제 링크] : https://www.acmicpc.net/problem/17472

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M;
int Arr[11][11];
int Cnt = 2;
int Dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int Parent[11];
bool Visit[11];
vector<pair<int, pair<int, int>>> V;
int Ans;

int get(int n){
    if (Parent[n] == n)	return n;
	else return get(Parent[n]);
}

void unionP(int a, int b) {
	a = get(a);
	b = get(b);
	if(a < b){
        Parent[b] = a;
    }
	else{
        Parent[a] = b;
    }
    return;
}

bool search(int a, int b) {
	a = get(a);
	b = get(b);
	if(a == b){
        return true;
    }
	else{
        return false;
    }
}

void count(int y, int x){
    queue<pair<int, int>> Q;
    Q.push({y, x});
    Arr[y][x] = Cnt;

    while(Q.empty() == false){
        int a = Q.front().first;
        int b = Q.front().second;
        Q.pop();

        for(int i=0; i<4; i++){
            int ny = a + Dir[i][0];
            int nx = b + Dir[i][1];
            
            if(ny < 0 || ny >= N || nx < 0 || nx >= M){
                continue;
            }
            if(Arr[ny][nx] == 1){
                Q.push({ny, nx});
                Arr[ny][nx] = Cnt;
            }

        }
    }
    Cnt++;
    return;
}

void find(int y, int x, int d){
    int dis = 0;
    int val = Arr[y][x];

    while(true){
        y += Dir[d][0];
        x += Dir[d][1];

        if(y < 0 || y >= N || x < 0 || x >= M || Arr[y][x] == val){
            return;
        }
        if(Arr[y][x]== 0){
            dis++;
        }
        else{
            if(dis > 1){
                V.push_back({dis, {val, Arr[y][x]}});
            }
            return;
        }
    }
    return;
}

int main(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> Arr[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(Arr[i][j] == 1){
                count(i, j);
            }
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            for(int d=0; d<4; d++){
                if(Arr[i][j] != 0){
                    find(i, j, d);
                }
            }
        }
    }

    sort(V.begin(), V.end());

    for(int i=0; i<10; i++){
		Parent[i] = i;
	}

	for(int i=0; i<V.size(); i++){
		if(search(V[i].second.first, V[i].second.second) == false){
			Ans += V[i].first;
			unionP(V[i].second.first, V[i].second.second);
		}
	}

	int p = get(2);
	for(int i=3; i<Cnt; i++){
		if(p != get(i)){
			Ans = 0;
        }
    }

	if(Ans == 0){
		cout << "-1\n";
    }
	else{
		cout << Ans << "\n";
    }

    return 0;
}