[BOJ]1707번 : 이분 그래프 (c++)

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

방법 1: BFS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool bfs(vector<vector<int>> &graph)
{
	const int COLOR_A = 1;
	int len = graph.size();
	
	// color : 색 구분을 표시할 벡터
	vector<int> color(len);
	queue<int> q;

	/*
		그래프가 비연결 그래프일 수도 있으므로
		전체 노드를 탐색하며 아직 방문하지 않은 그래프를 큐에 push
	*/
	for (int i = 1; i < len; ++i)
	{
		if (color[i] == 0)
		{
			color[i] = COLOR_A;
			q.push(i);

			while (!q.empty())
			{
				int node = q.front(); 
				q.pop();

				// 자식 노드를 탐색해서 큐에 push여부를 결정
				for (int j = 0; j < graph[node].size(); ++j)
				{
					int next = graph[node][j];
					
					// 자식 노드의 색이 없으면 --> 현재 노드와 다른 색을 입히고 큐에 push
					if (color[next] == 0)
					{
						color[next] = color[node] * -1;
						q.push(next);
					}
					// 자식 노드의 색이 현재 노드와 자식 노드의 색이 같으면 --> false 반환
					else if (color[node] == color[next])
					{
						return false;
					}
				}
			}
		}
	}

	return true;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// K : 테스트 케이스 개수
	int K;
	cin >> K;
	while (K--)
	{
		// V : 정점의 개수, E : 간선의 개수
		int V, E;
		cin >> V >> E;
		
		// 그래프 벡터 만들기
		vector<vector<int>> graph(V + 1, vector<int>());
		for (int i = 0; i < E; ++i)
		{
			int first, second;
			cin >> first >> second;
			graph[first].push_back(second);
			graph[second].push_back(first);
		}

		// 이분그래프면 "YES", 아니면 "NO" 출력
		cout << (bfs(graph) ? "YES\n" : "NO\n");
	}

	return 0;
}

 

방법 2: DFS

#include <iostream>
#include <vector>

using namespace std;

const int COLOR_A = 1;

bool dfs(vector<vector<int>>& graph, vector<int> &color, int node)
{
	// 현재 노드의 자식 노드를 탐색
	for (int i = 0; i < graph[node].size(); ++i)
	{
		int next = graph[node][i];
		
		// 자식 노드가 아직 방문 전일때, 현재노드의 반대 색을 입히고 dfs재귀함수 호출
		if (color[next] == 0)
		{
			color[next] = color[node] * -1;
			if (dfs(graph, color, next) == false)
			{
				return false;
			}
		}
		// 자식 노드의 색이 현재 노드색과 같을 때 false 반환
		else if (color[next] == color[node])
		{
			return false;
		}
	}

	return true;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// K : 테스트 케이스 개수
	int K;
	cin >> K;
	while (K--)
	{
		// V : 정점의 개수, E : 간선의 개수
		int V, E;
		cin >> V >> E;

		// 그래프 벡터 만들기
		vector<vector<int>> graph(V + 1, vector<int>());
		for (int i = 0; i < E; ++i)
		{
			int first, second;
			cin >> first >> second;
			graph[first].push_back(second);
			graph[second].push_back(first);
		}

		/*
			그래프가 비연결 그래프일 수도 있으므로
			전체 노드를 탐색하며 아직 방문하지 않은 정점을 검사
		*/
		vector<int> color(V + 1);
		bool flag = true;
		for (int i = 1; i < graph.size(); ++i)
		{
			if (color[i] == 0)
			{
				color[i] = COLOR_A;
				if (dfs(graph, color, i) == false)
				{
					flag = false;
				}
			}
		}

		// 이분그래프면 "YES", 아니면 "NO" 출력
		cout << (flag ? "YES\n" : "NO\n");
	}

	return 0;
}

 

이 문제의 경우, BFS가 더 효율적이다. 

 

이분 그래프란, 서로 인접한 정점이 다른 색이다.

즉, 현재 노드와 자식 노드의 색이 달라야 한다. 

따라서 자식 노드의 색을 일괄적으로 처리할 수 있는 BFS로직이 더 적절하다.

해당 노드를 방문하기 전에 색만 판단해도 되기 때문에

P/F결과가 좀더 빨리 나온다.

 

 

 

이분 그래프를 많이 참고한 블로그 : 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog