drwolf1999   2년 전

아래코드가 좌표평면에 임의의 여러개의 점에 모두 다른 색을 입히고 초당 십자방향으로 1만큼씩 퍼트릴때 인접하면 섞이는것을

이차원배열을 bfs하면서 색이 만날때마다 Union_find하는걸 대략적으로 한건데요 이렇게 되면 시간복잡도가
O(N^2 * M log(M))인가요 O(N^2 * log(M))인가요??
배열크기는 N * N이고 색의 가짓수는 M입니다

yukariko   2년 전

O(N^2lgM) 이맞는것 같습니다.

union find의 복잡도가 액커만 이라 거의 상수로 봐도 무방합니다만..

drwolf1999   2년 전

@yukariko 아 감사합니다!!

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