1717번 - 집합의 표현
이전 작업 0이 했던 정보를 가지고 작업 1일때 YES or NO로 출력합니다.
만약 작업 1 a b 일때 union(a,x) || union(b,x)를 한적이 없었다면 parent배열은 자기 자신을 가리킬것이고 (대표노드였다면 자기자신) ,
union을 했다면 자기가 속한 집합의 대표 노드를 가리킬것입니다. 결론적으로 이전에 연결정보가 있었다면 parent배열은 같은 노드를 가리킨다.
그래서 작업 1을 할 때, parent 배열을 쓰면 O(1)로 바로 접근 가능한데, find()를 쓰면 재귀를 사용하지않나요?
물론 답이 출력시 find()를 활용해야 정답인데, parent배열로 출력 시 왜 오답이 뜰까요
제가 잘못 이해했기 때문에 틀렸을텐데, 이유좀 알려주세요..
union을 한다고 해서 기존의 두 집합 내의 모든 원소가 즉시 루트를 가리키게 되는 것이 아닙니다. find를 통해 루트까지 따라올라가본 뒤에야 그 경로 상의 모든 원소들의 parent가 비로소 새로운 루트가 되는 것이고, 이 과정을 거치지 않은 원소들은 기존의 parent(루트가 아닐 수 있는)를 그대로 가지고 있는 상태입니다.
와 맞네요..ㄷㄷ감사합니다
댓글을 작성하려면 로그인해야 합니다.
tpwls8122 4년 전
이전 작업 0이 했던 정보를 가지고 작업 1일때 YES or NO로 출력합니다.
만약 작업 1 a b 일때 union(a,x) || union(b,x)를 한적이 없었다면 parent배열은 자기 자신을 가리킬것이고 (대표노드였다면 자기자신) ,
union을 했다면 자기가 속한 집합의 대표 노드를 가리킬것입니다. 결론적으로 이전에 연결정보가 있었다면 parent배열은 같은 노드를 가리킨다.
그래서 작업 1을 할 때, parent 배열을 쓰면 O(1)로 바로 접근 가능한데, find()를 쓰면 재귀를 사용하지않나요?
물론 답이 출력시 find()를 활용해야 정답인데, parent배열로 출력 시 왜 오답이 뜰까요
제가 잘못 이해했기 때문에 틀렸을텐데, 이유좀 알려주세요..