[백준 4195] 친구 네트워크 (자바)

난이도 : 골드 2

 

유니온 파인드 문제입니다. 하지만 입력은 숫자가 아닌 문자열이 주어집니다.

map을 이용하여 각 이름(문자열)마다 숫자를 부여해줬습니다. 그리고 이 숫자를 기준으로 union-find를 했습니다.

count는 초기 값을 모두 1로 갖습니다. n1, n2가 가지는 count 값을 union을 할 때 대표에게 값을 몰아줍니다.

그리고 이 값을 출력합니다.

f번 다른 이름이 2개씩 들어올 수 있으므로 최대 배열 크기는 2*f로 했습니다.

---

전역 변수

int parent[] = 그룹의 대표를 나타내는 배열

int count[] = 친구의 수

 

함수

void main

입력을 받고 count와 parent 배열을 초기화해줍니다.

f번 입력을 받으며 map에 이름이 없을 경우에 문자열 이름과 번호를 put 해줍니다.

그리고 부여받은 번호를 토대로 union-find를 진행합니다.

union을 할 때 계산된 count값을 출력해줍니다.

(union 호출)

 

void union

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.

그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.

p2가 작을 때 p2가 대푯값이 되므로 count[p1]의 값을 count[p2]에 더해줍니다.

p1이 작을 때는 반대로 진행합니다.

 

int find

입력받은 수의 대푯값을 반환합니다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.