wansoram   7달 전

제가 생각한 알고리즘은 이러합니다.

1. 선분단위로 저장

2. 모든 선분 한 쌍씩 비교하여 겹친다면 union

3. union된 배열 데이터를 기반으로 그룹, 및 구성원 확인

이라고 생각했는데....

흠 뭐가 잘못된 것일까요.. 접근이 잘못된 것일까요?

 뒤로가기 누르시지 마시고 한번 부탁드리겠습니다.

koosaga   7달 전

일단 마지막에 그룹 체크하는 건 확실히 이상하네요. p[i]가 항상 루트라는 조건이 없으니 find(i)로 대체되어야 할 것이고 그룹이나 cnt를 세는 건 잘못됐습니다 p = {0, 5, 0} 같은 걸 생각해 보면..

선분 교차하는 건 틀릴 여지가 많은데, 여기서도 체크해보시기 바랍니다. (전 안봤어요) 특히 실수 연산은 항상 조심하시길...

koosaga   7달 전

접근에 대해서 궁금하시다면 접근 자체는 옳네요

wansoram   7달 전

아 그렇군요! union find에 대해 공부가 부족했나 봅니다.

답변달아주셔서 감사합니다. 좋은 하루되세요!!

댓글을 작성하려면 로그인해야 합니다.