백준 14868번 : 문명 - BFS Union&Find C++

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

14868번: 문명

#include <bits/stdc++.h>
using namespace std;

int n, k, area = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int arr[2001][2001];
int unf[100001];

int Find(int x) {
    if (unf[x] < 0) return x;
    
    return unf[x] = Find(unf[x]);
}

void merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    unf[x] = y;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    memset(unf, -1, sizeof(unf));

    int t = 0;
    int comp;

    queue<pair<int, int> > Q;
    queue<int> region;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        arr[a][b] = ++area;
        region.push(area);
        comp = arr[a][b];
        Q.push({ a,b });
    }


    int q = Q.size();
    for (int i = 0; i < q; i++) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
            if (arr[nx][ny] > 0) {
                merge(arr[x][y], arr[nx][ny]);
            }
        }
        Q.push({ x,y });
    }



    while (!region.empty() && Find(comp) == Find(region.front())) {
        region.pop();
    }
    if (region.empty()) {
        cout << t << '\n';
        return 0;
    }
  
    while (!Q.empty()) {
        int q = Q.size();
        for (int i = 0; i < q; i++) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;

                if (arr[nx][ny] == 0) {
                    arr[nx][ny] = arr[x][y];
                    Q.push({ nx, ny });
                }
                else if (Find(arr[x][y]) != Find(arr[nx][ny])) {
                    merge(arr[x][y], arr[nx][ny]);
                }
            }
        }
        t++;

        //인접한 곳에 union 되지 않은 영역 있는지 체크 
        q = Q.size();
        for (int i = 0; i < q; i++) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
                if (arr[nx][ny] > 0) {
                    merge(arr[x][y], arr[nx][ny]);
                }
            }
            Q.push({ x,y });
        }

		while (!region.empty() && Find(comp) == Find(region.front())) {
            region.pop();
        }
        if (region.empty()) {
            cout << t << '\n';
            return 0;
        }

    }
    
    return 0;
}

백준 14868번 : 문명