(C++) 백준1889: 선물교환

문제 링크

이 문제에서 저는 고려해야할 것을 정리했었습니다.

• 먼저, 선물을 2개 미만을 받는 친구들은 제일 먼저 제외한다.

1. 이 친구(선물을 2개 미만을 받은)가 선물 준 친구들의 리스트에서 자기 자신을 지운다.
   • 지워졌을때 선물 준 친구의 선물이 2 이하면, 이 친구도 제외한다.
2. 이 친구(선물을 2개 미만을 받은)에게 선물을 준 친구가 있다면 그 친구도 제외한다
   • 이유: 문제에서 "조교들은 모든 학생들이 두 개의 선물을 주고, 또한 모든 학생들이 정확히 두개의 선물만을 받도록" 하였기 때문이다.

이 과정이 반복되기에 저는 DFS나 BFS를 떠올렸습니다.

DFS로 실행했더니 메모리 초과가 났고, segment fault가 떴지만 수정을 위한 코드 추적이 힘들었습니다ㅠ

그래서 BFS로 다시 새롭게 풀었습니다.

선물을 2개 미만을 받는 친구들은 제일 먼저 큐에 넣어주고 큐가 빌 때까지 돌려줬습니다.

그 전에 먼저 sendInfo와 receiveInfo라는 2차원 벡터에 선물을 준 사람들의 목록과 선물을 누군가에게 받았는지에 대한 목록을 만들어서 정보를 저장해줬습니다.

이 부분에서!! 저는 원래 map을 활용하여 저장해줬습니다.

그랬더니 결과는 시간 초과!
레드블랙트리 알고리즘을 활용하여 데이터가 들어오고 삭제될 때마다 정렬해주는 map의 특성이 발목을 잡은 케이스입니다.
map을 활용하여 코드 짜기는 쉬웠지만, 시간적으로는 최악이었죠.
그래서 2차원 벡터로 바꿔주었습니다.
2차원 벡터로 바꿔주었더니 시간 차이가 훨씬 줄어들었습니다.

이러한 로직을 반복하면서 방문처리를 하여 확인했던 친구들에게 재방문하지 않도록! 해줍니다.

제외되는 친구들은 ans라는 벡터에 넣어줍니다.

후에 n명 중에 ans에 담겨진 친구들의 명수를 제외하여 나타내주고,
방문하지 않은 친구들(2보다 적어지지 않는 친구들)의 번호를 출력해줍니다.

최종 코드

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

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	std::cout.tie(0);
}

//참여하는 학생 벡터
vector<int> ans;
int visited[200001];
//준 정보
vector<vector<int>> sendInfo;
//받은 정보
vector<vector<int>> receiveInfo;
int n;
void Check() {
	queue<int> que;
	for (int i = 1; i <= n; i++) {
		if (receiveInfo[i].size() < 2) {
			que.push(i);
		}
	}
	while (!que.empty()) {
		int qFront = que.front();
		que.pop();
		if (visited[qFront]) continue;
		visited[qFront] = true;
		//1. 내가 선물을 준 친구들의 리스트에서 내 이름을 뺀다.
		for (int i = 0; i < sendInfo[qFront].size(); i++) {
			int presentTo = sendInfo[qFront][i];
			receiveInfo[presentTo].erase(
				remove(receiveInfo[presentTo].begin(),
					receiveInfo[presentTo].end(), qFront),
				receiveInfo[presentTo].end());
			//만약에 이 친구가 내가 없으면 2보다 작아진다? 당장 큐에 넣어
			if (receiveInfo[presentTo].size() < 2)
				que.push(presentTo);

		}
		//2. 나에게 선물을 준 친구를 제거해야한다.
		for (int i = 0; i < receiveInfo[qFront].size(); i++) {
			que.push(receiveInfo[qFront][i]);
		}
		//해당 친구는 희망이 없으니 지워준다.
		ans.push_back(qFront);
	}
}

int main() {
	init();
	cin >> n;
	for (int i = 0; i <= n; i++) {
		sendInfo.push_back(vector<int>());
		receiveInfo.push_back(vector<int>());
	}
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		sendInfo[i].push_back(x);
		sendInfo[i].push_back(y);
        
		receiveInfo[x].push_back(i);
		receiveInfo[y].push_back(i);

	}
	Check();
	cout << (n - (int)ans.size()) << "\n";
	for (int i = 1; i <= n; i++) {
		if(!visited[i])cout << i << " ";
	}

}