SHA256
47 lines
2.3 KiB
Typst
47 lines
2.3 KiB
Typst
#import "연구실실습일지작성양식.typ": 실습일지
|
|
|
|
#실습일지(
|
|
소속대학: "공과대학",
|
|
소속학과: "컴퓨터소프트웨어학부",
|
|
학번: "2024062806",
|
|
성명: "주하진",
|
|
일시: "2026년 10월 2일 13시 부터 ~ 16시 까지",
|
|
내용: [
|
|
이번엔 DFS를 풀어보고 싶어서 *뿌요뿌요*를 봤습니다. 하지만 이 문제는 DFS로도 풀 수 있지만, 실제로 Union-Find를 이용하는 것이 더 간단한 것으로 보여서 Union-Find를 이용해서 풀었습니다.
|
|
|
|
Union-Find는 Disjoint Set을 관리하는 자료구조로 말 그대로 `union`과 `find`라는 두 가지 연산을 통해서 다른 집합을 합치거나 특정 원소가 속한 집합을 찾는 연산을 수행할 수 있습니다.
|
|
|
|
이 문제에서 뿌요뿌요 블럭의 연결된 블럭들을 Union-Find를 이용해서 관리하면, 각 블럭이 속한 집합의 크기를 쉽게 알 수 있고 쉽게 합칠 수 있습니다.
|
|
|
|
일단 `parents` 배열과 `counts` 배열을 만듭니다.
|
|
|
|
```rust
|
|
let n = field.len();
|
|
let mut parents = (0..n * n).collect::<Vec<usize>>();
|
|
let mut counts = vec![1; n * n];
|
|
```
|
|
|
|
그리고 `union`과 `find`를 이용해서 연결부분을 찾습니다. 그리고 이 연결부분을 `union`합니다. 이때 `union`에서는 일반적인 Union-Find와 다르게 `counts`와 관련된 특수한 처리를 해줘야 합니다. 왜냐하면 `union`을 할 때, 두 집합의 크기를 합쳐야 하기 때문입니다.
|
|
|
|
```rust
|
|
let current = field[i][j]; // foreach i, j
|
|
let index = i * n + j; // because of 1D representation
|
|
if i > 0 && field[i - 1][j] == current {
|
|
union(&mut parents, &mut counts, index, (i - 1) * n + j);
|
|
}
|
|
if j > 0 && field[i][j - 1] == current {
|
|
union(&mut parents, &mut counts, index, i * n + (j - 1));
|
|
}
|
|
```
|
|
이제 모든 components를 찾고 blastable한 컴포넌트를 찾고 그 개수를 새로 그중 `counts`가 가장 큰 컴포넌트를 찾으면 됩니다.
|
|
```rust
|
|
let comps = (0..n * n).map(|i| find(&mut parents, i)).collect::<HashSet<usize>>();
|
|
let count = comps.iter().filter(|&&x| counts[x] >= 4).count();
|
|
let maxima = comps.iter().map(|&x| counts[x]).max().unwrap_or(0);
|
|
(count, maxima)
|
|
```
|
|
|
|
|
|
],
|
|
)
|