[G4] 백준 1043번 거짓말 C++ 유니온-파인드

리뷰

 

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

아ㅏㅏ 진짜 맞왜틀 맞왜틀 했는데 커스텀 정렬 함수에서 경로 압축이 제대로 되지 않은게 문제였다.

결국 코드 리뷰를 통해 해당 부분에 대한 문제를 인식하고 고쳐서 AC를 받았다.

근데 브루트포스로 풀어도 0ms로 AC를 받는듯 하다.

오랜만에 주석을 빡세게 달았던 문제

 

 

전역 변수

• n : 사람의 수를 저장하기 위한 변수
• m : 파티의 수를 저장하기 위한 변수
• k : 진실을 이미 알고 있는 사람의 수를 저장하기 위한 변수
• ans : 진실을 아무도 모르는 파티의 개수를 저장하기 위한 변수
• nodes : 각 사람이 속한 그룹을 나타내기 위한 정수형 배열
• parties : 파티에 참가한 사람들의 정보를 저장하기 위한 정수형 벡터 배열

 

함수

1. compare

bool compare(int a, int b)

 

파티에 참여한 사람을 정렬하기 위한 커스텀 정렬 함수

1. 두 사람의 번호를 매개변수 a, b로 입력 받는다.
2. a와 b의 nodes배열에 저장된 값을 기준으로 오름차순 정렬해준다.
3. 이 때 Find를 통해 경로 압축을 진행해 주어야 한다.

 

2. Find

int Find(int a)

 

해당 번호를 가진 사람의 그룹 번호를 찾기 위한 함수

1. 탐색을 하기 위한 사람의 번호를 매개변수 a로 입력 받는다.
2. 만약 a가 현재 속한 그룹이 a와 동일하다면 a를 리턴해 준다.
3. 아닐 경우 a가 현재 속한 그룹을 재귀를 통해 갱신해 준다.

 

3. Union

void Union(int a, int b)

 

두 사람의 그룹을 합쳐주기 위한 함수

1. 두 사람의 번호를 매개변수 a, b로 입력 받는다.
2. 정수형 변수 A, B에 a, b를 각각 Find함수의 매개변수로 전달하여 받은 리턴값을 저장한다.
3. 만약 A와 B가 동일하다면 이미 같은 그룹이므로 리턴해 준다.
4. 같은 그룹이 아닌 경우 B가 속한 그룹을 A그룹으로 합쳐준다.

 

문제풀이

1. n, m값을 입력 받고 1 ~ n번 까지의 사람의 속한 그룹을 자기 자신으로 초기화한다.
2. k값을 입력 받고, k명의 사람의 번호를 변수 a로입력 받는다.
3. a번 사람의 nodes배열의 값을 0으로 바꿔줌으로 진실을 아는 그룹에 속하도록 변경해준다.
4. m개의 파티 정보를 입력 받아주고, 각 파티마다 참여한 인원을 parties벡터에 push_back해준다.
5. sort메서드를 통해 현재 파티 정보를 compare함수를 사용하여 정렬해 준다.
6. nodes배열의 value가 가장 낮은 한명을 기준으로 파티에 참여한 인원 모두 그룹화를 진행한다.
7. 모든 파티 정보와 그룹화가 끝난 경우 다시 m개의 파티 정보를 순회해 준다.
8. 만약 각 파티의 참여 인원 중 그룹이 0번인 사람이 한명도 없을 경우 ans를 증가시켜 준다.
9. 모든 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. compare 함수에서 값을 리턴할 때 nodes의 a, b인덱스를 참조하였더니 AC를 받지 못했다.
2. Find를 씌워 경로 압축을 진행한 값을 비교하였더니 AC를 받게 되었다.

 

참고 사항

• Union을 처리할 때 그룹 번호를 기준으로 오름차순 정렬된 상태이므로 만약 진실을 아는 사람이 있을 경우 해당 파티에 속한 인원은 모두 진실을 알게 된다.

 

정답 코드

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

int n, m, k, ans;
int nodes[51];
vector<int> parties[51];

// 유니온-파인드 함수
int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

// 그룹 번호가 낮은 순서로 정렬하기 위한 커스텀 정렬 함수
bool compare(int a, int b) {
	return Find(nodes[a]) < Find(nodes[b]);
}

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

	cin >> n >> m;
	// 1 ~ n번 까지의 사람의 속한 그룹을 자기 자신으로 초기화
	for (int i = 1; i <= n; ++i) nodes[i] = i;

	// k명의 사람은 진실을 알고있음을 명시, 0번 그룹인 사람들은 진실을 알고 있는 사람들의 그룹으로 가정
	cin >> k;
	while (k--) {
		int a; cin >> a;
		// a번의 사람의 value를 0으로 바꿔줌으로 진실을 아는 그룹에 속하도록 변경
		nodes[a] = 0;
	}

	// m개의 파티 정보를 입력 받음
	for (int i = 0; i < m; ++i) {
		// i번 파티에 참여한 a명의 참여자를 parties의 i번째 벡터에 추가
		int a; cin >> a;
		while (a--) {
			int b; cin >> b;
			parties[i].push_back(b);
		}

		// nodes배열의 value가 낮은 순으로 정렬, value가 0인 경우(진실을 아는 경우) 맨 앞으로 오게 됨
		sort(parties[i].begin(), parties[i].end(), compare);

		// nodes배열의 value가 가장 낮은 한명을 기준으로 파티에 참여한 인원 모두 그룹화를 진행
		// 만약 진실을 아는 사람이 있을 경우 해당 파티에 속한 인원은 모두 진실을 알게 된다.
		for (int j = 1; j < parties[i].size(); ++j) Union(parties[i][0], parties[i][j]);
	}

	// m개의 파티 정보를 다시 순회하며 현재 파티에 진실을 아는 사람이 존재하는지 체크
	for (int i = 0; i < m; ++i) {
		bool flag = 1;

		// 파티 참여 인원을 모두 체크
		for (int j = 0; j < parties[i].size(); ++j) {
			// 그룹이 0번인 사람이 있을 경우 해당 파티는 pass
			if (!Find(parties[i][j])) {
				flag = 0;
				//break;
			}
		}
		if (flag) ans++;
	}
	cout << ans;
}