[BOJ] 3830 교수님은 기다리지 않는다

3830

문제의 조건

N, M이 주어지고,
2<=N<=100,000 : 샘플 종류 개수
1<=M<=100,000 : Input 개수
0<=w<=1,000,000 : 무게

• 무게를 잰 경우 ! a b w (b 가 a보다 w그램 무겁다.)
• 교수님의 질문 ? a b (b가 a보다 얼마나 무거운지 출력, 모르면 UNKNOWN 출력)
• 마지막 줄: 0 0

---

접근 방식

a와 b는 비교가 가능하다. --> a와 b가 들어올 경우, 서로 무게를 계산할 수 있다.
b와 c는 비교가 가능하다. --> a 와 c 역시 비교가 가능하다. b에 비해 c가 얼마나 무거운지(w) 알 수 있기 때문.
즉, 직접적으로 비교되지 않았더라도, 한 다리 이상 건너서 비교된 적 있으면 그 사이에서는 비교가 가능하다.
맨 처음 들어온 a 를 0으로 두고, 거기서 +- 하는 식으로 얼마만큼 무거운지 파악할 수 있다.
--> 한다리 이상 건너서 비교된 적이 있다 == disjoint-set 에서 같은 그룹이다.
--> 비교된 적 없다 (UNKNOWN) == disjoint-set 이 같은 그룹이 아니다.

---

코드

disjoint-set 을 구현할 수 있으면 생각보다 많이 어려운 문제는 아니다 :D
계산이 쪼금 귀찮을뿐!