[알고리즘/문제풀이][BOJ 1707번] 이분 그래프

이분 그래프 문제는 그래프 탐색 알고리즘과 이분 그래프의 정의를 이용하여 해결할 수 있는 문제입니다. 구체적으로 어떻게 해결할 수 있는지에 대해서는 후술 할 내용을 통해 차근차근 탐구해보겠습니다.

이분 그래프는 각각의 집합에 속하는 모든 정점들이 서로 연결되지 않도록 그래프의 모든 정점을 두 개의 집합에 속하도록 나눌 수 있는 그래프를 의미합니다. 즉, 하나의 간선에 대해 한 쪽에서는 집합 1의 정점이 연결되어 있을 때 다른 쪽에는 반드시 집합 2의 정점이 연결되어야만 합니다.

그래프 탐색 알고리즘으로 사용할 BFS는 하나의 정점에서 시작하여 도달할 수 있는 그래프의 모든 정점을 탐색하는 알고리즘입니다. BFS가 그래프를 탐색할 때는 하나의 정점와 간선으로 연결된 모든 정점를 탐색합니다. 이분그래프의 정의와 연관지어 생각하면 BFS가 발견한 정점은 탐색 기준 정점과 다른 집합에 속해있어야 한다는 사실을 알 수 있습니다. 이러한 사실에 기반을 두고 BFS를 계속 진행하면서 먼저 발견되지 않은 정점들을 발견하면 다른 집합에 소속되도록 하고 이미 발견된 정점을 발견했을 때는 소속 집합을 비교하여 같은지 확인해야 합니다. 만약 소속 집합이 같다면 이 그래프는 이분 그래프의 정의를 만족시키지 못하는 그래프라고 판단할 수 있습니다.

만약 해당 그래프가 이분 그래프라면 어떠한 정점을 시작으로 위의 BFS 과정을 통해 어떠한 충돌없이 모든 정점을 적합하게 집합에 소속시킬 수 있어야 합니다.

해당 문제의 코드를 구현할 때 주의할 부분이 있다. 정점의 개수가 최대 20000개, 간선의 개수가 20만개이기 때문에 인접행렬이나 단순한 배열 기반의 인접 리스트로 구현할 수 없다. 낭비되는 메모리가 많아 필연적으로 허용된 메모리 크기를 초과하기 때문이다. 따라서 동적 할당 기반 인접 리스트를 사용해야 한다. 이때 C언어 기준 malloc을 사용하면 구현을 가능하나 많은 시간이 걸린다. 뿐만 아니라 메모리 해제 문제를 발생시킨다. 해당 문제에서는 이러한 부분이 제한으로 걸리지 않으나 앞으로 비슷한 문제를 풀게 될 때를 생각하면 더 나은 방법을 궁리해야 한다. 

메모리 풀 방식을 사용하면 malloc을 사용한 동적 할당보다 더 빠르게 입력을 처리할 수 있다. 메모리 풀은 사용할 메모리를 전역변수로 미리 선언해 놓고 필요할 때 해당 메모리를 끌어 쓰는 방식이다.  

작성한 코드는 다음과 같다.

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable : 4996)
//메모리풀 방식으로 해결가능 -> 동적할당 대신 필요할 메모리를 미리 전역변수 영역에 선언

int K, V, E;
int src, dest;
int visit[20020];
int color[20020];
int isNO;

int wp, rp;
int queue[20020];

/*메모리 풀 방식을 위해 선언해야 하는 부분
struct node pool[400020];
int pos = 0;
*/

struct node {
	int v;
	struct node* next;
};

struct node *graph[20020];

void add(int temp1, int temp2)
{
	struct node* temp;
	struct node* head;
    
	/*메모리 풀 방식을 위해 선언해야 하는 부분
	temp = &pool[pos++];
	temp->v = temp2;
	temp->next = NULL;
	*/

	temp = (struct node*)malloc(sizeof(struct node));
	temp->v = temp2;
	temp->next = NULL;

	if (graph[temp1] == NULL) {
		graph[temp1] = temp;
	}
	else {
		head = graph[temp1];
		graph[temp1] = temp;
		temp->next = head;
	}

	return;
}

void BFS(int start) {
	visit[start] = 1;
	color[start] = 0;
	queue[wp++] = start;

	while (rp != wp) {
		int target = queue[rp++];
		struct node* head_target = graph[target];

		while (head_target != NULL) {
			if (visit[head_target->v] == 1) {
				if (color[head_target->v] == color[target]) {
					isNO = 1;
					return;
				}
				head_target = head_target->next;
			}
			else {
				color[head_target->v] = (color[target] + 1) % 2;
				visit[head_target->v] = 1;
				queue[wp++] = head_target->v;
				head_target = head_target->next;
			}
		}
	}
}

void init() {
	for (int i = 1; i <= V; i++) {
		visit[i] = 0;
		color[i] = -1;
		graph[i] = NULL;
	}
	wp = 0;
	rp = 0;
	isNO = 0;
    //pos=0;
}

int main(void) {
	scanf("%d", &K);
	
	for (int i = 0; i < K; i++) {
		scanf("%d %d", &V, &E);
		init();

		for (int j = 0; j < E; j++) {
			scanf("%d %d", &src, &dest);
			add(src, dest);
			add(dest, src);
		}

		for (int i = 1; i <= V; i++) {
			if (visit[i] == 0) {
				BFS(i);
				if (isNO == 1) break;
			}
		}
		
		if (isNO == 1) printf("NO\n");
		else printf("YES\n");
	}


}

문제는 다음의 링크에서 확인할 수 있다.

https://www.acmicpc.net/board/view/43886