1707 - 이분그래프

(기본적인 bfs, dfs문제 + 인접 노드별로 다른 색깔 할당)해주는 문제이다.

이분그래프란

이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

• 쉽게 말하면 모든 노드 기준으로 하나의 노드와 인접해있는 노드는 다른 색을 칠해야한다

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

queue <pair<int, char>> q; // blue : b, yellow : y
vector<vector<int>> v;
bool visited[20001];
char arr[20001];
int ans;
int K;
int V, E;
int a, b;

void bfs(int start) {
	
	visited[start] = true;
	arr[start] = 'r';
	q.push({ start,'r'});
	while (!q.empty()) {
		int node = q.front().first;
		char color = q.front().second;
		q.pop();
		if (color == 'r') { color = 'y'; }
		else { color = 'r'; }
		for (int i = 0; i < v[node].size(); i++) {
			int next = v[node][i];
			
			if (!visited[next]) {
				visited[next] = true;
				
				q.push({ next,color });
				arr[next] = color;
			}
		}

	}
	
}


void init() {
	ans = 1;
	v.resize(V+1); // V+1;체크하기

	for (int i = 0; i < E; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	memset(visited, 0, sizeof(visited));
}

int check() {
	
	for (int i = 1; i <= V; i++) {
		int v_size = v[i].size();
		for (int j = 0; j < v_size; j++) {
			int next = v[i][j];
			if (arr[i] == arr[next]) { return 0; }
		}
	}
	return 1;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> K;
	while (K--) {
		cin >> V >> E;
		init();
		for (int i = 1; i <= V; i++) {
			if (!visited[i]) {bfs(i);}
		}
		
		if (check()) {	cout << "YES"<<'\n';}
		else {cout << "NO"<<'\n';}
		v.clear();
	}
	
	return 0;
}

---

메모리 줄이기

1. vector<vector<int>> v;
2. vector<int> v[20001];
   1의 방법이 메모리가 6316KB로 2의방법 11568KB의 공간보다 훨씬 단축되었다. 2의 방법은 안쓰는 벡터 공간을 할당해줬기 때문에 공간 낭비가 되고 있다.

• 놓친 점

1. vector<vector<int>> v; 초기화를할 때 v.resize(V+1);로 공간을 할당해주고 끝났을때는 v.clear();를 통해 초기화 해줘야한다.
2. memset을 쓰기위해서는 #include <cstring>