(H1632 - Rank Transform of a Matrix) 순서 강제 + Union-Find

이 문제를 rule-based 풀이로 풀려고 하면 답이 없음.

왜냐면, 한 row 혹은 column의 rank를 맞춰놔도, 다른 row 혹은 column에 의해 영향을 받을 수 있기 때문.

 

풀이의 핵심 논리는 아래 포스팅에 잘 설명되어 있다.

https://leetcode.com/problems/rank-transform-of-a-matrix/discuss/1390964/DSUUF-Approach-Explained-in-Detail-%2B-Intuitions-%2B-Diagrams-%2B-Python3-Annotated-Code

 

💡 핵심 :

정렬해서 순서 강제 (낮은 숫자부터 rank 매기기)

+ Union-Find (같은 숫자는 같은 rank)

+ Hint 2 (row, col 단위로 rank 관리)

 

1. 배열의 최솟값에 rank 1이 매겨지는 것은 자명하다. 그리고 숫자가 커질수록 rank가 높아질 확률이 있겠지.

→ 작은 숫자들부터 rank 매기자. 순서 강제. 

 

구현 : map<숫자, 위치배열> 식으로 오름차순 정렬된 상태로 숫자별 위치 정리해서 오름차순 처리

 

 

2. 동일 row, col에 있는 같은 숫자는 동일한 rank를 매겨야 한다는 조건

→Union-Find 사용해서 동일 row, col에 있는 같은 숫자는 같은 그룹으로 묶고, 그룹별로 rank 매기자.

 

구현 : 각 row와 column을 각각 그룹으로 본다.

row N + col M 크기의 DisjointSet 생성 후, (x,y)에 숫자가 나타날 경우 row x와 col y를 같은 그룹으로 묶는다.

이러면 나중에 또 x나 y에 같은 숫자 나타나도 동일 그룹에 있는 걸로 처리되겠지.

 

 

3. 각 cell별로 rank 매기는게 아니라, row/col 단위로 max rank 관리

→ 1번 조건에 의해 rank는 계속 증가하는 방향으로 업데이트 됨 + Hint2를 생각하면 이 방식으로 맞는 rank를 찾아낸다는 것을 알 수 있음

 

구현 : vi rank(N + M, 0), group_rank(N + M, 0);

group_rank는 약간 중간 계산 값을 저장하기 위한 tmp 공간 느낌

 

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
    int N = matrix.size(), M = matrix[0].size();
    auto to_pos = [&](int x, int y) { return x * M + y; };

    vector<vector<int>> ans(N, vi(M, 0));
    map<int, vector<pii>> d; // value : {locations in (x,y)}

    // 1. Init - sort using map
    FOR(x, 0, N) FOR(y, 0, M) {
        d[matrix[x][y]].emplace_back(x, y);
    }


    vi rank(N + M, 0); // track max ranks of row (idx 0~N-1) & col (idx N~)
    vi group_rank(N + M, 0); // rank assigned
    // ★ rank는 0으로 초기화 - 업데이트 시 max에 안걸리게

    // From smallest number
    for (const auto& kv : d) {
        int num = kv.first;
        const vector<pii>& v = kv.second;

        // 2. Find groups
        DisjointSet dsu(N+M); // ★ track connected rows and cols
        for (const pii& p : v) {
            auto [x, y] = p;
            dsu.Union(x, N + y); // row 'x' and column 'y' connected by current element
        }

        // 3. Find group rank
        for (const pii& p : v) {
            auto [x, y] = p;
            int g = dsu.Find(x);
            int& gRank = group_rank[g];
            gRank = max({ gRank, rank[x] + 1, rank[N + y] + 1 });
        }

        // 4. Update result and fill ans
        for (const pii& p : v) {
            auto [x, y] = p;
            int g = dsu.Find(x);
            int gRank = group_rank[g];
            rank[x] = max(rank[x], gRank);
            rank[N + y] = max(rank[N + y], gRank);

            ans[x][y] = gRank;
        }
    }

    return ans;
}