2610번 - 회의준비
union find 알고리즘을 사용하신 분들을 대상으로 말씀드립니다.
결론부터 이야기하면 이웃하는 두 숫자를 받아 union 한 뒤 마지막에 다시한번 set 을 업데이트 시켜주세요
예를 들어 현재 set 이 [0,1,1,2,2] 인 상태라고 하겠습니다. (0번 인덱스는 버리는 값)
이경우 1,2번과 3,4번이 각각 한 셋입니다.
이때 마지막에 (2,3) 인 데이터가 들어와 union 해주면 set은 [0,1,1,1,2] 로 바뀝니다.
그러면 2,3 이 합쳐졌으니 1,2,3,4 번이 전부 한 셋이지만 [0,1,1,1,2] 로 저장되어 있기 때문에 2개로 보입니다.
따라서 set의 모든 원소에 get_parent 함수를 다시 실행시켜 set을 업데이트 시켜줘야 합니다.
혹시 python 을 사용하시는 분들 중에
map(get_parent, set) 만 사용하면 업데이트가 되지않고 (set 은 그대로고 새로운 map 객체를 반환하기 때문입니다.)
set = list(map(get_parent, set)) 를 사용해야 set이 업데이트 됩니다. 제가 저지른 실수라 참고해주세용...
댓글을 작성하려면 로그인해야 합니다.
an3735297 1년 전 1
union find 알고리즘을 사용하신 분들을 대상으로 말씀드립니다.
결론부터 이야기하면 이웃하는 두 숫자를 받아 union 한 뒤 마지막에 다시한번 set 을 업데이트 시켜주세요
예를 들어 현재 set 이 [0,1,1,2,2] 인 상태라고 하겠습니다. (0번 인덱스는 버리는 값)
이경우 1,2번과 3,4번이 각각 한 셋입니다.
이때 마지막에 (2,3) 인 데이터가 들어와 union 해주면 set은 [0,1,1,1,2] 로 바뀝니다.
그러면 2,3 이 합쳐졌으니 1,2,3,4 번이 전부 한 셋이지만 [0,1,1,1,2] 로 저장되어 있기 때문에 2개로 보입니다.
따라서 set의 모든 원소에 get_parent 함수를 다시 실행시켜 set을 업데이트 시켜줘야 합니다.
혹시 python 을 사용하시는 분들 중에
map(get_parent, set) 만 사용하면 업데이트가 되지않고 (set 은 그대로고 새로운 map 객체를 반환하기 때문입니다.)
set = list(map(get_parent, set)) 를 사용해야 set이 업데이트 됩니다. 제가 저지른 실수라 참고해주세용...