[C++][Goorm][탐색] 카드 교환하기

구름EDU - 모두를 위한 맞춤형 IT교육

 

 

 

사람들이 번호가 적힌 카드를 갖고 있는데, 이 번호가 자신의 번호랑 최대한 비슷해야 한다.

친구관계의 사람들은 카드를 교환할 수 있다.

자신의 번호랑 카드의 번호의 차이를 불만족도라고 하는데, 이 불만족도가 가장 적은 합의 경우를 구해서 최소 불만족도 값을 출력하면 된다.

 

사람들의 수와 카드번호는 1보다 크며, 친구관계가 없을 수도 있다.

---

*해결법

1) 친구관계를 표현한 행렬을 만들고 조합을 구할 때, 친구관계이면 해당 조합을 선택해서 불만족값을 구하는 방법

2) 친구관계면 카드를 다 교환할 수 있으므로, DFS로 친구관계를 구하고 그 친구들의 카드를 오름차순 정렬시키는 방법

2) 방법을 그림으로 표현하면 위와 같다.

 

1번~4번 사람이 존재하고 1-2번, 2-3번이 친구사이이다. 1~4번이 들고 있는 카드는 3, 1, 5, 4번 이다.

1~3번이 서로 연결된 친구관계이기 때문에 이들은 카드를 마구 바꿀 수 있다.

이 때, 불만족도를 최소로 갖게 하려면 카드를 오름차순 정렬한 후(1, 3, 5) 순서대로 1,2,3번이 갖게 하는 것이 가장 작은 값일 것이다.(4번 친구는 친구관계가 없으므로 카드를 교환할 수 없다.)

즉, 최소 불만족도는 위와 같이 카드를 교환했을 때이고 3을 출력하면 된다.

 

*알아둘 것

1) 벡터 크기 부여하며 생성하는 법

vector<int> v(5); //크기5인 벡터 생성

vector<int> v(5, 0); // 5크기로 만들고 0으로 초기화

 

2) 벡터로 그래프/트리 관계 표현하는 법

vector<int> *graph = new vector<int>[3];

graph[0].push_back(1);
graph[1].push_back(0);
graph[0].push_back(2);
graph[2].push_back(0);

즉, 0 1 이 연결되어 있다고 주어지면, 1배열 값에 0 도 벡터로 추가해주면 된다.

 

3) 벡터 resize

vector<int> v;

v.resize(5, 0);

5 크기로 재설정하고 0으로 초기화하기

 

*코드

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

vector<int> cardGroup, personGroup;
vector<bool> visited;

void DFS(int currentPerson, vector<int> cards, vector<int> *relations){
	cardGroup.push_back(cards[currentPerson]);
	personGroup.push_back(currentPerson);
	
	for(auto& next: relations[currentPerson]){
		if(visited[next]) continue;
		visited[next] = true;
		DFS(next, cards, relations);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int personNum, relationNum;
	long long answer = 0;
	cin >> personNum >> relationNum;
	
	//카드 정보 받기
	vector<int> cards(personNum + 1);
	for(int i = 1; i <= personNum; i++){
		cin >> cards[i];
	}
	
	//관계를 벡터행렬로 표현
	int person1, person2;
	vector<int> *relations = new vector<int>[personNum + 1];
	for(int i = 0; i < relationNum; i++){
		cin >> person1 >> person2;
		relations[person1].push_back(person2);
		relations[person2].push_back(person1);
	}
	
	//BFS로 연결되어 있는 사람들 찾기
	visited.resize(personNum, false);
	for(int i = 1; i <= personNum; i++){
		if(visited[i]) continue;
		
		visited[i] = true;
		DFS(i, cards, relations);
		
		//정렬하기
		sort(cardGroup.begin(), cardGroup.end());
		sort(personGroup.begin(), personGroup.end());
		
		//불만족도 구하기
		for(int j = 0; j < cardGroup.size(); j++){
			answer += abs(cardGroup[j] - personGroup[j]);
		}
		cardGroup.clear();
		personGroup.clear();
	}
	
	//정답출력
	cout << answer;
	
	return 0;
}

근데 10, 12번이 틀렸고 28 ~ 59까지 타임아웃.........................