(BOJ 2933 미네랄) Union-Find 활용 + 중력

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

 

풀이 아이디어를 정리해보자.

 

문제 진행 과정

1. 막대 던진다

2. 미네랄 제거

   (→ 해당 row의 leftmost/rightmost 'x' 제거)

// Step 1. Throw stick, destroy mineral
if (left){
    for (char& c : board[h]){
        if (c == 'x') {
            c = '.';
            break;
        }
    }
    left = false;
}
else{
    for(int idx = C-1; idx >= 0; idx--){
        char& c = board[h][idx];
        if (c == 'x') {
            c = '.';
            break;
        }
    }
    left = true;
}

 

3. 클러스터 정리 

• 클러스터 판별
  (→ Union-Find로 각 'x'의 집합 정해주기)

// Step 2. Identify clusters
DisjointSet g(R * C);
 
auto to_pos = [&](int x, int y) { return (R * C - 1) - (x * C + y); };
auto boundary_0 = [&](int x, int y) {return 0 <= x && x < R && 0 <= y && y < C; };
 
// ★ Order is important (from bottom to top) - to ensure bottom groups are propagated
for (int x = R - 1; x >= 0; x--) for (int y = C - 1; y >= 0; y--) {
    if (board[x][y] == '.') continue;
 
    for (int i = 0; i < 4; i++) {
        int xn = x + "1210"[i] - '1'; // E S W N
        int yn = y + "2101"[i] - '1';
 
        if (!boundary_0(xn, yn) || board[xn][yn] == '.') continue;
 
        g.Union(to_pos(x, y), to_pos(xn, yn));
    }
}

 

• 바닥과 연결되어있지 않은 클러스터 떨어뜨리기
  (→ 바닥 집합에 포함되지 않은 'x'를 떨어뜨릴 클러스터로 판단;
       한꺼번에 떨어뜨리기 위해 최소 거리 falling 구한 뒤 떨)

// Step 3. Apply gravity to those that are not connected to the ground ★
// Ground numbers : 0, 1, 2, ..., C-1
bottom = vi(C, R - 1);
int fall = INF;
vector<pii> cluster; // cluster to fall
for (int x = R - 1; x >= 0; x--) for (int y = C - 1; y >= 0; y--) {
    if (board[x][y] == '.') continue;
 
    // ★ [Fix] find falling range - to make whole cluster fall together
    if (g.Find(to_pos(x, y)) >= C) {
        fall = min(fall, bottom[y] - x);
        cluster.emplace_back(x, y);
    }
    else {
        bottom[y] = x - 1;
    }
}
 
// Execute falling
for (pii& p : cluster) {
    auto [x, y] = p;
    board[x][y] = '.';
    board[x + fall][y] = 'x';
}

 

 

 

어려운 점

1. '떨어뜨릴 클러스터를 어떻게 판별할 것인가'

→ 클러스터는 Union-Find로 구분 (그룹이 다르면 다른 클러스터).

바닥에 붙어있는 그룹들이 있는데, 이 그룹에 속하지 않은 클러스터가 있다? = 공중에 떠 있음. 떨어뜨리기

 

2. '어떻게 한꺼번에 떨어뜨릴 것인가'

→ 하나씩 떨어뜨리면 클러스터 부서짐.

클러스터 맨 아래 레이어의 원소들이 떨어질 거리 중 최소값만으로 전체 클러스터가 떨어져야 함.

 

---

오랜만에 Union-Find 써보는거라 Union 개념을 헷갈림.

그냥 두 집합 간에 Union 한번만 써주면, 각 집합 내에 있는 원소들 모두에 적용됨

(왜? Find는 집합의 root를 찾아주는데, Find를 이용해서 두 root를 Union 하니까)

 

BOJ 백조의 호수 풀었던 경험이 Union-Find에 익숙해지는데 도움이 됐던 것 같음!https://goldenriver42.tistory.com/39?category=943305