백준 4195번: 친구 네트워크

 

 

 

 

 

 

 

 

union-find를 활용한 문제다.

 

*** Union-find 개념 ***

https://gimmesome.tistory.com/34?category=1103655

[1주차] Union-find

 

 

 

 

 

 

검색한 블로그를 참고하여 풀었다.

참고한 포스트 주소 : https://jaimemin.tistory.com/771

 

 

 

 

 

 

다음과 같이 생각해봄. 

 

1. 친구 두명의 이름이 입력되면 연결되어있다는 것임
2. 이름의 부모노드를 해당하는 arr에 넣기 위해 이름마다 arr의 인덱스를 할당해줘야함
3. 2를 위해선 이름마다 arr의 인덱스를 pair시켜야 하므로, map을 사용해야함. map<이름, arr인덱스>
4. 친구 네트워크의 친구 수는 root의 arr값과 같음으로 트리의 root의 arr절대값을 출력함.

 

 

 

 

---

맵 기본 함수

 

기본형태

• map<key,value> : key와 value를 pair 형태로 선언합니다.

 

iterator(반복자)

• begin() : beginning iterator를 반환
• end() : end iterator를 반환

 

추가 및 삭제

• insert( make_pair(key,value) ) : 맵에 원소를 pair 형태로 추가
• erase(key) : 맵에서 key(키값)에 해당하는 원소 삭제
• clear() : 맵의 원소들 모두 삭제

 

조회

• find(key) : key(키값)에 해당하는 iterator를 반환
• count(key) : key(키값)에 해당하는 원소들(value들)의 갯수를 반환

 

기타

• empty() : 맵이 비어있으면 true 아니면 false를 반환
• size() : 맵 원소들의 수를 반환

---

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cstring>	//memset
using namespace std;

int arr[100001];
int F;

int findParent(int num) {
	if (arr[num] < 0)
		return num;
	int parent = findParent(arr[num]);
	arr[num] = parent;
	return parent;
}


void merge(int aParent, int bParent) {
	if (abs(arr[aParent]) >= abs(arr[bParent])) {
		arr[aParent] += arr[bParent];
		arr[bParent] = aParent;
	}
	else {
		arr[bParent] += arr[aParent];
		arr[aParent] = bParent;
	}
	
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int test_case;
	cin >> test_case;
	
	for (int i = 0; i < test_case; i++) {

		cin >> F;

		//for문보다 실행속도가 빠름
		memset(arr, -1, sizeof(arr));

		//map을 통해 사람 파악
		map<string, int>name;	//pair 정의
		int idx = 1;	
		//arr[0]엔 값이 안들어감 (-1임)

		for (int i = 0; i < F; i++) {

			string a, b;
			cin >> a >> b;
			
			//새로나온 이름이라면 인덱스 부여
			if (name.count(a) == 0 )
				name[a] = idx++;
			if (name.count(b) == 0)
				name[b] = idx++;
		
			//루트를 찾음
			int aParent = findParent(name[a]);
			int bParent = findParent(name[b]);

			//같은 집합 내에 있다면
			if (aParent == bParent)
				cout << abs(arr[aParent]) << "\n";
			//다른 집합이라면 합친 뒤
			else
			{
				merge(aParent, bParent);
				//root가 되는 노드의 arr값이 트리의 크기
				if (arr[aParent] < 0)
					cout << abs(arr[aParent]) << "\n";
				else
					cout << abs(arr[bParent]) << "\n";
			}
		}
	}

	return 0;
}

 

 

 

 

 

---

발생 에러

1. 런타임 에러

• 처음에 arr의 초깃값을 for문을 사용해 -1로 채웠더니 에러가 발생
• memset( arr, -1, sizeor(arr)) 을 사용하니 에러가 사라지고 시간초과 에러 발생
• memset은 for문보다 실행속도가 빠름.

 

2. 시간 초과

• endl을 \n으로 바꿨더니 시간초과에러 사라짐
• endl은 개행만 해주는 것이 아니라 내부 버퍼를 비워주는 역할도 함께 하기 때문에 매우 느림
• 속도를 줄일 방법이 더이상 없을 때 endl을 \n으로 바꾸고 정답이 뜰 수 있음
• C++을 쓰면서 입출력 방식은 C를 지향하자.

---