metadata   2년 전

우선 알고리즘을 설명하자면

이 문제의 케이스들을 반대로 돌려 보면 전형적인 Union-Find가 된다는 점에 착안해

정말 반대로 돌렸습니다.


결과는 초반 테스트 케이스에서 TLE이고요,

아직 무한루프 TLE인지 알고리즘 TLE인지 판별을 못 했습니다.


만약 알고리즘 TLE라면 의심가는 부분이 하나 있긴 한데,

Union-Find의 두 가지 요소 중 하나인 Collapsing Find를 구현 방법을 까먹어서

단순히 현재 찾는 노드를 루트에 갖다붙이는 식으로밖에 처리해주지 않았다는 점입니다.


과연 그 부분이 문제인가요? 그렇다면 Collapsing Find를 어떤 방식으로 구현해야 좋을까요?

아니면 다른 부분에서 문제될 만한 부분이 있나요?

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