핵심 아이디어

<aside> 💡

연결을 끊는 것은 어렵다. 연결하는 것은 쉽다.

쿼리가 들어온 순서의 반대부터 처리한다.

즉, 쿼리를 이미 있는 선을 지우는 것으로 생각하여 선이 끊고 있던 양쪽의 영역이 이어지는 것으로 생각할 수 있다.

이렇게 처리한 결과를 다시 역순으로 출력하면 본 문제의 정답이 된다.

</aside>

연결여부를 저장하는 것은 분리집합(유니온 파인드)를 이용하면 된다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int p[1'000'100];

int Find(int x)
{
    if(x == p[x]) return x;
    else return p[x] = Find(p[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);

    if(x != y) p[y] = x;
}

int n, m, q;
int a[1'005][1'005];

vector<tuple<int, int, int, int>> qry;

bool v[1'005][1'005];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};

int num(int x, int y) {return (x-1)*m+(y-1);}

void dfs(int x, int y)
{
    v[x][y] = true;

    for(int t = 0; t<4; t++){
        int nx = x+dx[t];
        int ny = y+dy[t];

        if(a[nx][ny] || v[nx][ny]) continue;
        
        Union(num(x, y), num(nx, ny));
        dfs(nx, ny);
    }
}

void init()
{
    for(int i = 0; i<=n+1; i++){
        a[i][0] = 1e+9;
        a[i][m+1] = 1e+9;
    }
    for(int i = 0; i<=m+1; i++){
        a[0][i] = 1e+9;
        a[n+1][i] = 1e+9;
    }
    
    for(int i = 0; i<=n*m; i++) p[i] = i;
}

signed main()
{
    FASTIO;
    cin >> n >> m >> q;
    init();
    for(int i = 0; i<q; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        qry.push_back({x1, y1, x2, y2});
        
        if(x1 == x2){
            for(int j = y1; j<=y2; j++){
                a[x1][j]++;
            }
        }
        else{
            for(int j = x1; j<=x2; j++){
                a[j][y1]++;
            }
        }
    }

    int cnt = 0;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            if(v[i][j] || a[i][j]) continue;

            dfs(i, j);
            cnt++;
        }
    }
    vector<int> ans(q);
    ans[q-1] = cnt;
    for(int i = q-1; i>=1; i--){
        auto[x1, y1, x2, y2] = qry[i];
        
        if(x1 == x2){
            int x = x1;
            for(int y = y1; y<=y2; y++){
                a[x][y]--;

                if(a[x][y]) continue;
                bool flag = false;
                for(int t = 0; t<4; t++){
                    int nx = x+dx[t];
                    int ny = y+dy[t];

                    if(a[nx][ny] == 0){
                        flag = true;
                        if(Find(num(x, y)) != Find(num(nx, ny))){
                            Union(num(x,y), num(nx, ny));
                            if(!v[x][y]){
                                v[x][y] = true;
                                continue;
                            }

                            cnt--;
                        }
                    }
                }
                if(!flag) cnt++;
            }
        }
        else{
            int y = y2;
            for(int x = x1; x<=x2; x++){
                a[x][y]--;

                if(a[x][y]) continue;
                bool flag = false;
                for(int t = 0; t<4; t++){
                    int nx = x+dx[t];
                    int ny = y+dy[t];
                    

                    if(a[nx][ny] == 0){
                        flag = true;
                        if(Find(num(x, y)) != Find(num(nx, ny))){
                            Union(num(x,y), num(nx, ny));
                            if(!v[x][y]){
                                v[x][y] = true;
                                continue;
                            }

                            cnt--;
                        }
                    }
                }
                if(!flag) cnt++;
            }
        }

        ans[i-1] = cnt;
        // for(int i = 1; i<=n; i++){
        //     for(int j = 1; j<=m; j++){
        //         if(a[i][j])cout << "# ";
        //         else cout << ". ";
        //     }
        //     cout << "\\n";
        // }
        // cout <<cnt <<"--------\\n";
    }

    for(int i = 0; i<q; i++){
        cout << ans[i] <<"\\n";
    }
    
    return 0;
}

복기

각 칸에 쿼리가 들어온 횟수를 저장하고 케이스 워크를 통해 쿼리로 인해 유의미한 변화가 생긴 부분을 찾았다.

황교선 학생의 코드를 보니 쿼리를 저장할 때 유의미한 변화가 생긴 곳이 어디인지를 저장하여 훨씬 간단하게 구현할 수 있다는 것을 깨달았다.