[알고리즘] 백준 2146 - 다리 만들기

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

int N, L = 2;
int Arr[101][101];
bool Visit[101][101];
int Dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<pair<int, int>> V;
int Ans = 1234567890;

void land(int y, int x, int l){
    queue<pair<int, int>> Q;
    Q.push({y, x});
    Visit[y][x] = true;
    Arr[y][x] = l;

    while(Q.empty() == false){
        int cy = Q.front().first;
        int cx = Q.front().second;
        Q.pop();
        
        for(int i=0; i<4; i++){
            int ny = cy + Dir[i][0];
            int nx = cx + Dir[i][1];
            
            if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if(Visit[ny][nx] == true || Arr[ny][nx] != 1) continue;
            
            Visit[ny][nx] = true;
            Arr[ny][nx] = l;
            Q.push({ny, nx});

        }
    }
    return;
}

int solve(int n){
    int res = 0;
    queue<pair<int, int>> Q;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(Arr[i][j] == n){
                Visit[i][j] = true;
                Q.push({i, j});
            }
        }
    }

    while(Q.empty() == false){
        int s = Q.size();
        for(int i=0; i<s; i++){
            int y = Q.front().first;
            int x = Q.front().second;
            Q.pop();
            
            for(int j=0; j<4; j++){
                int ny = y + Dir[j][0];
                int nx = x + Dir[j][1];
                
                if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
                if(Arr[ny][nx] != 0 && Arr[ny][nx] != n) return res;
                else if(Arr[ny][nx] == 0 && Visit[ny][nx] == false){
                    Visit[ny][nx] = true;
                    Q.push({ny, nx});
                }
            }
        }
        res++;
    }
    return res;
}

int main(){
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> Arr[i][j];
            if(Arr[i][j] == 1){
                V.push_back({i, j});
            }
        }
    }

    for(int i=0; i<V.size(); i++){
        int y = V[i].first;
        int x = V[i].second;
        
        if(Visit[y][x] == true) continue;
        
        land(y, x, L);
        L++;
    }

    for(int i=2; i<L; i++){
        memset(Visit, false, sizeof(Visit));
        Ans = min(Ans, solve(i));
    }

    cout << Ans << "\n";

    return 0;
}