백준 1707 - 이분 그래프

문제링크

• 백준 1707

문제설명

• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
• 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

문제접근

• 이분 그래프란 에서 이분 그래프의 개념을 먼저 파악했다.
• 완전탐색(DFS, BFS) 을 통해 방문하는 노드에는 서로 다른 색을 칠하는데, 만약 인접한 노드에 같은 색이 이미 칠해져 있다면 이분 그래프가 아니다.
• 모든 노드가 하나의 그래프로 이루어지지 않을 수 있고, 이분 그래프끼리는 서로 독립적이기 때문에 언제나 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있다.

구현1 (DFS)

#include <iostream>
#include <vector>
#include <memory.h>

#define MAX_V 20001
using namespace std;

vector<int> graph[MAX_V];
bool visited[MAX_V];
int colorInfo[MAX_V];
bool flag = true;

// color 는 0 과 1만 존재
void dfs(int cnode, int color)
{
	for (int i = 0; i < graph[cnode].size(); i++)
	{
		int nNode = graph[cnode][i];
		if (visited[nNode] == true) // 방문한 적이 있는 경우
		{
			// 현재 노드의 색깔과 인접한 노드의 색깔이 같은 경우 이분 그래프가 아님
			if (colorInfo[nNode] == colorInfo[cnode])
			{
				flag = false;
				return;
			}
		}
		else
		{
			visited[nNode] = true;
			colorInfo[nNode] = (int)!color;
			dfs(nNode, (int)!color);
		}
	}
}

void Init()
{
	flag = true;
	memset(visited, false, sizeof(visited));
	memset(colorInfo, 0, sizeof(colorInfo));
	for (int i = 0; i < MAX_V; i++)
	{
		graph[i].clear();
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int K;
	cin >> K;

	for (int testCase = 0; testCase < K; testCase++)
	{
		Init();
		int v, e;
		cin >> v >> e;
		for (int i = 0; i < e; i++)
		{
			int from, to;
			cin >> from >> to;
			graph[from].push_back(to);
			graph[to].push_back(from);
		}
		
		// 색이 정해지지 않은 노드를 찾고 dfs
		for (int node = 1; node <= v; node++)
		{
			if (visited[node] == false)
			{
				visited[node] = true;
				colorInfo[node] = 0;
				dfs(node, 0);
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

구현2(BFS)

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>

#define MAX_V 20001
using namespace std;

vector<int> graph[MAX_V];
bool visited[MAX_V];
int colorInfo[MAX_V];
bool flag = true;

void bfs(int sNode)
{
	queue<pair<int, int>> q;
	q.push(make_pair(sNode, 0)); // 첫 노드 색깔은 0으로 칠한다.
	visited[sNode] = true;
	colorInfo[sNode] = 0;

	while (!q.empty())
	{
		pair<int, int> cNode = q.front();
		q.pop();
		
		int cIdx = cNode.first;
		int cColor = cNode.second;
		for (int i = 0; i < graph[cIdx].size(); i++)
		{
			int nIdx = graph[cIdx][i];
			// 방문한 적이 있는 경우 -> 색깔 확인
			if (visited[nIdx] == true)
			{
				if (colorInfo[nIdx] == cColor)
				{
					flag = false;
					break;
				}
			}
			else
			{
				int nColor = (int)!cColor;
				visited[nIdx] = true;
				colorInfo[nIdx] = nColor;
				q.push(make_pair(nIdx, nColor));
			}
		}
		if (flag == false) break;
	}
}

void Init()
{
	flag = true;
	memset(visited, false, sizeof(visited));
	memset(colorInfo, 0, sizeof(colorInfo));
	for (int i = 0; i < MAX_V; i++)
	{
		graph[i].clear();
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int K;
	cin >> K;

	for (int testCase = 0; testCase < K; testCase++)
	{
		Init();
		int v, e;
		cin >> v >> e;
		for (int i = 0; i < e; i++)
		{
			int from, to;
			cin >> from >> to;
			graph[from].push_back(to);
			graph[to].push_back(from);
		}
		
		// 색이 정해지지 않은 노드를 찾고 bfs
		for (int node = 1; node <= v; node++)
		{
			if (flag == false) break;
			if (visited[node] == false) bfs(node);
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}