스톤헤드 부수기

난이도 : 골드 2 유니온 파인드 문제입니다. 하지만 입력은 숫자가 아닌 문자열이 주어집니다. map을 이용하여 각 이름(문자열)마다 숫자를 부여해줬습니다. 그리고 이 숫자를 기준으로 union-find를 했습니다. count는 초기 값을 모두 1로 갖습니다. n1, n2가 가지는 count 값을 union을 할 때 대표에게 값을 몰아줍니다. 그리고 이 값을 출력합니다. f번 다른 이름이 2개씩 들어올 수 있으므로 최대 배열 크기는 2*f로 했습니다. 전역 변수 int parent[] = 그룹의 대표를 나타내는 배열 int count[] = 친구의 수 함수 void main 입력을 받고 count와 parent 배열을 초기화해줍니다. f번 입력을 받으며 map에 이름이 없을 경우에 문자열 이름과 번호를 ..

난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다. 유니온은 도시들을 묶고 파인드는 이러한 도시의 대표를 찾습니다. 그룹의 대표를 그 그룹에서 가장 작은 값으로 정했습니다. 대표는 그룹마다 통일성을 가진다면 어떤 값으로 해도 상관은 없습니다. 단, 이 대표를 통하여 그룹을 구분할 수 있어야 합니다. 예를 들면 [1, 2, 3, 4, 7, 8], [5, 6], [9]의 그룹은 각 그룹의 대표를 1, 5, 9로 설정합니다. 각 그룹의 대표를 저장하는 parent배열을 위와 같이 나타내 볼 수 있습니다. 최적화를 위해 그룹의 대표를 건드릴 때는 find를 이용합니다. parent 절대 xx..