[18116] 로봇 조립

https://www.acmicpc.net/problem/18116

18116번: 로봇 조립

기본적인 유니온 파인드 문제다. 대신 문제에서 요구하는 것은 부품이 속한 컴포넌트의 크기이다. 

 

풀이

부품의 번호가 1부터 1,000,000이기에 입력 인덱스를 바로 핸들링 하기 위해 1,000,001 개의 배열을 생성. 초기값을 -1로 둔다. 여기서 -1은 루트라는 것을 표시함과 동시에 컴포넌트의 개수를 음수로 표현하는 역할도 하게 된다.

파인드에 해당하는 root() 함수를 통해 배열의 값을 탐색, 값이 0보다 작으면 루트인 것으로 판정, 0보다 큰 값이면 해당 부품의 부모인 것으로 판정하고 부모의 루트를 재귀 호출하여 컴포넌트의 루트를 탐색한다.

유니온에 해당하는 union() 함수는 둘의 루트를 확인 후, 서로 다른 컴포넌트라면 합치는 과정을 수행하는데, 루트가 될 노드에 추가될 노드의 값을 더해주는 것으로 컴포넌트의 크기를 갱신하게 되고, 다른 컴포넌트로 편입하게 될 루트에는 해당 루트의 번호를 대입해주는 것으로 편입을 마치면 된다. 

마지막으로 출력해야 할 경우에는 해당 부품의 루트를 찾고, 루트를 인덱스로 배열의 음수 값을 절댓값으로 출력해주면 된다.

 

정답 코드