https://www.acmicpc.net/problem/25200
문제 요약
- 흥미로웠던 문제
- 1 ~ N 음료수가 있음(N 30만)
- M개의 차원이 있음(M 30만)
- 각각의 차원에서 한 종류의 음료수 변환이 발생함 u -> v
- M개의 차원을 통과한 후 각각의 음료수는 어떻게 변환이 되었을까?
- 공식해설 이 있는데 나와는 접근법이 다름
접근법
- 하나씩 수행해보면 되겠지만 N*M 시간이 걸릴 것임
- 변환된 음료수에 원래 음료수들의 값이 매달려 있다고 생각해봄
- (변환된 음료수) - (원래 음료수들)
- 초기 1 - 1, 2 - 2, 3 - 3
- 1번째 차원에서 2 -> 3 변환이 발생하면
- 1 - 1, 2 - 없음, 3 - 3, 2
- 2번째 차원에서 3 -> 1 변환이 발생하면
- 1 - 없음, 2 - 없음, 3- 3, 2, 1
- 변환이 발생할때 매달려 있는 음료수들을 변환이 발생할 곳으로 통째로 옮겨줌
- 링크드리스트 같은 발상
- 더 생각을 하다보면 union-find로 접근이 가능함
- 그룹들을 합치고, 그룹의 대표가 어디에 속하는지, 변환된 음료수에는 어떤 대표 음료수를 갖고 있는지
- 변환이 발생할때마다 그룹들이 합쳐질 것임
- u -> v 변환이면 u에 속한 그룹이 v에 속한 그룹으로 합쳐짐
- 합쳐진 그룹의 대표 -> v 표시
- v -> 합쳐진 그룹 대표 표시
- u -> 아무것도 없음 표시
newbieski