이미 푸셨겟지만 팁을 드리자면,
사람수 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}의 경우가 될겁니다.
이런 경우의 수를 잘생각해보면 해법이 보일겁니다.
ksoosung77 2년 전 1
처음에 Union&find 할려다 중간에 어떤 친구는 빼먹어도 문제가 없다는 것을 안 이후로 큰 좌절감을 느끼고 이제 어떻게 해야할지 눈에 안보여서 이렇게 남겨봅니다.