질문] "3830_교수님은 기다리지 않는다" 왜 유니온 파인드일까요?

3830 교수님은 기다리지 않는다

문제 중 어떤 내용 때문에 유니온 파인드를 떠올리셨는지 여쭤보고자 글을 남깁니다.

저는 처음 문제를 읽고,

1. 두 샘플을 고른 뒤, 무게를 잰다.
2. 실험실에서 한 일이 순서대로 주어진다. 이때 두 샘플의 무게 차이는?
3. ! a b w와 같은 형식으로 주어진다. 이 뜻은 b가 a보다 w그램 무겁다는 뜻이다
4. 교수님의 질문은 ? a b와 같은 형식으로 주어진다. 이 뜻은 b가 a보다 얼마나 무거운지를 출력하라는 뜻이다.

위의 네 가지를 보고 유니온 파인드를 떠올렸는데요.
백준 집합의 표현과도 비슷한 듯보였습니다.

강사님 블로그 + 다른 분들 블로그에서 LCA를 먼저 떠올린 분들도 있다고 하는데요..

여러분들은 처음 이 문제에 어떻게 접근하셨나요?

---

아래는 백준 유니온 파인드 관련 문제 4가지입니다! 함께 보시면 좋을 것 같아 올립니다.
유니온 파인드 관련 문제

[wjdgns7712]

저는 출력에서 UNKNOWN을 고려해야한다는 부분에서 union/find를 떠올렸고, 굳이 트리의 깊이까지 고려할 필요가 없다고 생각해서 LCA는 염두에 두지 않았던것같아요!

[BuriGori]

저는 입력으로 주어지는 (! a b w) 와 (? a b)라는 점에서 유니온 파인드를 떠올렸습니다.
왜냐하면 특정 a와 b라는 두 지점이 연산(무게 비교)되지 않았거나, a또는 b가 연결된 다른 지점과 연관지어 생각하는 경우 a와 b 자체가 연결되어 있지 않다면 값을 구할 수 없기 때문에 그룹화라는 아이디어가 떠올랐습니다.

@wjdgns7712 @BuriGori 답변 달아주신 내용으로 문제를 다시 읽어보니 유니온 파인드 개념 정리가 다시 되네요! 답변 감사드립니다 :> 해당 이슈는 오늘 자정 이후에 닫겠습니다!