ksoosung77   2년 전

처음에 Union&find 할려다 중간에 어떤 친구는 빼먹어도 문제가 없다는 것을 안 이후로 큰 좌절감을 느끼고 이제 어떻게 해야할지 눈에 안보여서 이렇게 남겨봅니다.

hsw0194   2년 전

이미 푸셨겟지만 팁을 드리자면,

사람수 n명중에서 어느 사람들 A,B,C,D가 있다고 할때

A는 B가 가야지 가고,

B는 C가 가야지 가고,

...

D는 A가 가야지 가는 상황이 발생합니다.

다시 말해서 A->B->C->D->A 라는 cycle이 발생하게 됩니다.

이럴때는 A,B,C,D는 갈꺼면 한번에 다 태워야 합니다.

Union find로 구성을 했다면 다음와 같은 점을 주의해야 합니다.

A,B,C,D는 하나의 집합으로 묶이는데 , A만을 바라보는 X와, X만을 바라보는 Y가 있다고 합시다.

그럴때 탑승가능한 케이스는 {A,B,C,D} 혹은 {A,B,C,D,X} 혹은 {A,B,C,D,X,Y}의 경우가 될겁니다.

이런 경우의 수를 잘생각해보면 해법이 보일겁니다.

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