백준 1717번 집합의 표현

< 백준 1717번 집합의 표현 - 마포 코딩박 >

사용한 알고리즘: Union-Find


 유니온 파인드를 구현하라는 문제였습니다. 0이 입력되면 union, 1이 입력되면 find 연산을 하면 됩니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~8)
 'A[x] : x의 root' 로 설정하여 각 수들의 root 를 판별해 주었습니다.
 ( x 자기 자신이 root 인 경우 A[x]=-1 < 0 으로 설정하고, 초기 시작시 모든 점은 자기자신을 root로 합니다.)

(2) (코드 9~16)
 find 를 구현하는 함수입니다.
 A[x]<0 인 경우 해당 x 가 root 임을 활용합니다.

(3) (코드 17~23)
 union 을 구현하는 함수입니다.