https://www.acmicpc.net/problem/31933
문제 요약
- 마을과(N) 마을을 이어주는 강(M). (N,M 5000)
- 연어 K개. (K 50만)
- 연어는 크기가 있음. (1 ~ 1000000000)
- 강은 l, r이 있고, l <= 연어크기 <= r이어야 강을 건넘
- 1번 마을 -> N 번 마을까지 갈 수 있는 연어의 개수 구하기
접근법
- 연어 하나씩 해보면 답은 나올 것임. 하지만 시간 복잡도..
- 연어를 크기순으로 정렬했다고 봤을때,
- 어떤 강의 l을 기준으로 어떤 연어들은 작을 것이고(모두 못건넘)
- 어떤 연어들은 클 것임(일단 건널 수는 있음. r을 더 봐야겠지만)
- 두 개의 우선순위 큐를 준비함(MINQ)
- 아직 다리에 사용되지 않은 것들
- 다리에 사용 된 것들
- 연어들을 크기가 작은 것부터 보는데
- 다리에 사용되지 않은 것들
- l이 가장 작은 다리와 크기를 비교해서
- l <= 연어크기면 이 다리는 앞으로 사용할 수 있음(뒤에 나올 연어는 다 크니까)
- 다리에 사용된 것들
- r이 가장 작은 다리와 크기를 비교해서
- r < 연어크기이면 이 다리는 앞으로 사용할 수 없음(뒤에 나올 연어는 다 크니까)
- 다리에 사용되지 않은 것들
- 다리에 변경사항이 생기면 1 -> N까지 갈 수 있는지 체크함
- BFS를 사용하든, union-find를 사용하든
- 사용 가능한 다리만 이용해서 탐색
- 변경사항이 생길때만 체크하고 그 외에는 체크하지 않음
- 변경사항은 최대 2*N번 생김(다리가 사용가능, 사용 불가능)
- 시간 복잡도 O(klogk) + O(NlogN)
newbieski