codingismylife   1년 전

처음에 파티가 하나씩 열릴 때마다 parent 배열(대표 노드 저장 배열)을 초기화해서 각 파티를 확인하는 걸로 코드를 짰다가, 답이 계속 이상하게 나오길래 모든 파티에 대해 Union 연산을 수행한 후에, 진실을 알고 있는 사람들과 비교해서 다시 짰더니 정답을 받았습니다

그냥 당연하게 모든 파티에 대해 Union을 실행한다고 생각하면 되나요??

처음에 파티가 하나씩 열릴 때마다 Union을 하고 다시 대표 배열을 초기화하는지, 모든 파티에 대해 Union을 하고 답을 구해야 하는지 문제에서 확신을 얻지 못해서 이 부분은 어떻게 알아내야 하는 건지 궁금합니다....

not_strober   1년 전

모든 파티에 대해 Union 연산을 먼저 해야 합니다.
같은 파티에 있는 사람끼리는 모두 진실을 알거나 알지 못하거나 둘 중 하나입니다. 이건 Union으로 그 사람들을 하나의 집합에 묶는 것으로 생각할 수 있습니다. 만약 Union을 한 이후에 한 집합에 진실을 아는 사람이 한 명 이상 있다면 그 집합은 모두 진실을 아는 사람들의 집합이 됩니다. 반대로 집합의 누구도 진실을 모른다면 진실을 모르는 사람들의 집합이 됩니다.
따라서 코드에서 구현하신 것처럼 각 파티 별로 한 명씩만 Find로 부모를 비교해 주면 그 파티가 진실을 아는 파티인지 아닌지 알 수 있습니다.

codingismylife   1년 전

감사합니다!! 시간은 걸려도 직접 해보니까 모든 파티에 대해서 해야 말씀하신 것처럼 진실을 알고 있는 사람과 이전에 같이 파티를 했던 사람들도 결국 진실을 알게 되면서 소문이 퍼져나가는 구조로 된다는 것을 명확히 이해했습니다^^

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