[G2] 백준 4195번 친구 네트워크 C++ 유니온-파인드, 해시맵

리뷰

 

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

해시맵을 사용해 문자열을 key로 그룹을 구분하고, 매 번 Union처리 후 그룹의 크기를 구해주는 문제

항상 정수로 그룹을 구분했던 문제에 비해 신박했던 문제

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 정수형 변수
• f : 각 테스트 케이스 마다 친구 관계의 개수를 저장할 정수형 변수
• G : 그룹의 크기를 나타내기 위한 해시맵
• F : 그룹의 루트를 저장하기 위한 해시맵

 

함수

1. Find

string Find(const string& a)

 

현재 a가 속한 그룹의 루트의 이름을 구하기 위한 함수

1. 매개 변수로 탐색을 진행할 친구의 이름 a를 전달 받는다.
2. 만약  F[a]가 a와 같다면 a를 리턴해 준다.
3. 아니라면 F[a]를 Find함수에 F[a]를 전달하여 재귀를 통해 경로압축을 진행해 준다.

 

2. Union

void Union(const string& a, const string& b)

 

두 친구가 속한 그룹을 하나로 합치기 위한 함수

1. 매개 변수로 그룹화를 위한 두 친구의 이름 a, b를 전달 받는다.
2. 문자열 변수 A, B에 Find함수를 통해 a, b의 부모를 각각 구하여 저장해 준다.
3. 만약 F[A]와 F[B]가 같다면 이미 부모가 같은 경우이므로 도중에 return 처리를 해준다.
4. 부모가 같지 않다면 F[B]의 값을 a로, G[A]에 G[B]의 크기만큼 더해주어 그룹화를 진행해 준다.

 

문제풀이

1. t값을 입력 받고, t번의 while문을 통해 테스트케이스를 반복해 준다.
2. 매 테스트 케이스 마다 f값을 입력 받아주고, 이미 사용했던 G와 F의 초기화를 진행해 준다.
3. f번의 while문을 개행하고, 매 루프마다 문자열 변수 a, b에 두 친구의 이름을 입력 받아준다.
4. 만약 a가 b보다 크다면 swap 함수를 통해 a와 b의 값을 변경해 주어 a가 항상 작도록 유지해 준다.
5. 만약 G[a]의 value가 0이라면 G[a]의 값을 1로, F[a]의 값을 a로 변경해 준다, b도 동일하게 진행해 준다.
6. Union함수에 a, b를 전달하여 그룹화가 가능하다면 그룹화를, 아니라면 그냥 return하게 둔다.
7. F[b]를 Find함수에 전달하여 경로 압축을 진행하고 리턴 받은 문자열을 G의 key로 활용해 그룹의 크기를 출력한다.

 

트러블 슈팅

1. 예제 중 두번째 테스트 케이스의 값이 정답과 다르게 2, 2, 3이 출력되었다.
2. Union함수에서 그룹화 처리 시 G[A]++로 작성한 로직을 G[A] += G[B]로 변경해 주었더니 AC를 받았다.

 

참고 사항

• 그룹의 일관성 유지를 위해 swap함수를 통해 항상 a가 작은 값이 오도록 변경해 주었다.
• 해시맵은 그룹 인덱싱만 해주고 로직을 배열로 처리한다면 메모리와 시간을 더욱 아낄 수 있을 것 같긴 하다.

 

정답 코드

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;

int t, f;
unordered_map<string, int> G;
unordered_map<string, string> F;

string Find(const string& a) {
	if (F[a] == a) return a;
	return F[a] = Find(F[a]);
}

void Union(const string& a, const string& b) {
	string A = Find(a);
	string B = Find(b);
	if (F[A] == F[B]) return;
	F[B] = a;
	G[A] += G[B];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> f;
		G.clear();
		F.clear();

		while (f--) {
			string a, b; cin >> a >> b;
			if (a > b) swap(a, b);
			if (!G[a]) {
				G[a] = 1;
				F[a] = a;
			}
			if (!G[b]) {
				G[b] = 1;
				F[b] = b;
			}
			Union(a, b);
			cout << G[Find(F[b])] << "\n";
		}
	}
}