백준 1707 : 이분 그래프 ★

★★★★☆

알고리즘을 짜는건 어렵지않았지만 메모리 초과를 처리하는게 어려웠다..

개념

이분그래프는 그래프들의 정점의 집합을 서로 인접하지 않게 분할할 수 있는 그래프이다.
무슨 뜻이냐면, 2개의 색으로 그래프를 색칠할 때, 모든 정점들이 인접하는 정점과 다른 색을 가지고 칠해지는 것이다. (고등학교에서 확률 시간에 많이 봤던 느낌)

나의 풀이

• 이번 문제는 BFS를 가지고 풀이하기로 했다. '인접한' 정점들의 색을 칠하게 되기때문에,
  한 정점을 중심으로 인접한 정점들에 접근하는 BFS가 더 적합하다고 생각했다.

• visited의 값을 이전에는 bool 값으로 사용했지만, 이번에는 어떤 값이 채워져있는지를 알기 위해 int 배열로 선언하고,
  채워진 값들을 비교해 인접한 정점끼리의 값이 같다면 이분 그래프가 아니다! 라는 결론을 내도록 했다.

• 1회 결과를 내는 것은 비교적 쉬웠으나, 메모리를 처리하는 것이 어려웠다..
  기존에는 2차원배열을 이용하여 구현하였는데, 이번에는 정점의 최댓값이 증가하여
  무려 20000*20000 사이즈의 배열을 만들었어야 했으므로 메모리초과가 날 수밖에 없었다.
  => graph를 vector 배열로 수정해주었다.

• k번의 실행을 하는 동안, 초기에는 제대로된 값들이 나오다가 후반으로 갈수록 이상한 값들이 나왔는데, visited 배열과 graph 배열을 초기화해주지 않았기 때문이었다.
  => 초기화 함수 추가

• 매 실행마다 graph를 초기화해주는 과정에서, 기존에는 2중 for문을 사용하여 모든 정점 값을 초기화해주어야 했다면, 이제는 graph[i] 벡터를 clear해주기만 하면 되었다.

BFS에 대한 이해와 메모리에 대한 이해를 늘리기 위해서라도 다음에 다시 풀어봐야할 문제이다.

#include <iostream>
#include <queue>
#define MAX 20001
using namespace std;

int v, e;
vector<int> graph[MAX]; //벡터 배열
int visited[MAX]; //0,1,2 번갈아가면서 채워줄것
queue<int> q;

void init() { //배열을 초기화해주는 함수
	for (int i = 0; i <=v; i++) {
		visited[i] = 0;
		graph[i].clear();
	}
}

void bfs(int start, int tile) { //번갈아가면서 타일을 채움
	q.push(start);
	visited[start] = tile;
	//cout << start << "\n";
	//cout << "정점 " << start << " , " << visited[start] << " 채움 \n";


	while (!q.empty()) {
		int tem = q.front();
		q.pop();
		if (visited[tem] == 1) tile = 2; //현재 타일과 색이 겹치지 않도록, 칠해줄 색을 변경해줌
		else if (visited[tem] == 2) tile = 1;


		for (int i = 0; i <graph[tem].size(); i++) {
				if (visited[graph[tem][i]] == 0) {
					visited[graph[tem][i]] = tile;
					q.push(graph[tem][i]);
					//cout << "정점 " << graph[tem][i] << " , " << visited[graph[tem][i]] << " 채움 \n";
				}
			
		}
	}
	return;

}
int isBipartiete() { //이분그래프인지 확인하는 함수
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			if (visited[i] == visited[graph[i][j]]) { //인접한 정점과 같은 값이라면
				return -1; //이분 그래프가 아님
			}
		}
	}
	return 0;
}

int main() {
	int k;
	cin >> k;
	while (k > 0) {
		//cout << "\n\ncase " << 11-k << " ==========================\n";
		cin >> v >> e;

		for (int i = 0; i < e; i++) {
			int x, y;
			cin >> x >> y;

			graph[x].push_back(y);
			graph[y].push_back(x);
		}

		for (int i = 1; i <= v; i++) {
			if (visited[i] == 0) {
				bfs(i, 1); //기본 타일값을 1로 설정하여 bfs 진행
			}
		}

		if (isBipartiete() == -1) cout << "NO\n";
		else cout << "YES\n";
		
		init(); //벡터와 배열 초기화
		k--;
	}
}

참고

이분 그래프 개념
https://woovictory.github.io/2020/01/26/Bipartite-Graph/

반례, 벡터배열 사용
https://jdselectron.tistory.com/51