[백준/C++] 17619번: 개구리 점프(G2)

문제

https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

 

 

사용한 알고리즘

• 2022.02.17 - [PS/Algorithm] - [알고리즘 개념정리] 11. 분리집합/최소 신장 트리
• 스위핑? (아직 뭔지 잘 모르겠음)

 

 

풀이

통나무들의 (x1, x2) 좌표가 주어지는데 그게 겹치면 union 해주면 된다. (y좌표는 신경안써도됨)
Q로 들어오는 통나무 2개가 같은 집합이면 1을 출력하고 아니면 0을 출력한다.

---

첫번째 WA)
x1 기준으로 오름차순 정렬해주고 다음 통나무와 비교하여 겹치면 union 한다. (코드)

이렇게 풀면 다음과같은 반례가 생긴다. (출처)

그래서 이중for문으로 모든 쌍의 union을 시도해봐야하나 싶었는데
N이 100000 이라서 그건 아닌것 같았다.

생각해보니 저 상황에서 3번 통나무를 굳이 2번 통나무와 또 union을 할 필요가 없었다.
확인한 통나무 중에 x2 좌표가 가장 뒤에있는 통나무를 저장(필요시 갱신)해놓고
그 통나무와 union해주는 방식으로 풀면 O(N)에 풀 수 있을 것 같았다.

두번째 WA)
그래서 idx와 end에 x2가 가장 뒤에있는 통나무의 정보를 저장해주고 for문 하나로 풀어봤다.
(코드)

맞왜틀...이 아니라
sort 해줄거기때문에 통나무의 순번을 저장하고 관리해야하는데
그걸 안해줬다.;

세번째 풀이)
그부분만 수정하니까 AC였다. (코드)

 

---

 

이 문제를 이중for문으로 푸신분이 계시던데 그게 왜 가능한지 모르겠다. (링크)

출처 : https://david0506.tistory.com/83

출처 : https://david0506.tistory.com/83

모든 통나무가 인접한 경우(break 안함)에는 O(N^2)이 돼서 시간초과 나야하는거 아닌가..?
내일은 스위핑이 뭔지 공부해봐야겠다.