[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 이분 그래프 (1707)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 이분 그래프 (1707)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 이분 그래프 (1707)

 

---

 

1707번: 이분 그래프

[ 문제 ]

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

[ 입력 ]

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

[ 출력 ]

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

[ 제한 ]

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

---

[ 코드 1 ]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
vector <int> arr[20001]; // 간선 v의 최대값은 20000이기 때문 (index 제외하고 20001개)
int color[20001]; // 0은 아직 접근 안한 것, 1/2는 색깔구분
// 이 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록 2가지 색깔로 칠해주는 것 
// 처음 노드를 선택했을 때 1, 1로 칠해진 노드의 다음 노드를 선택했을 때 2 .. (반복)
 
void dfs(int node, int c) {
	color[node] = c; // true, false로 사용하고 안한것을 나눠주는 대신, 해당되는 번호(색깔)을 지정
 
	for (int i = 0; i < arr[node].size(); i++)
	{
		int next = arr[node][i];
		if (color[next] == 0)
		{
			dfs(next, 3 - c); 
			// 처음 노드라면 1이, 1의 다음 노드라면 2로 ...
		}
	}
}
 
int main() {
	int k; // k : 테스트케이스 개수
	cin >> k;
 
	while (k--)
	{
		int v, e; // v : 정점의 개수, e : 간선의 개수
		cin >> v >> e;
 
		/* 초기화 */
		for (int i = 1; i <= v; i++)
		{
			arr[i].clear(); // 인접리스트 (vector) 초기화
			color[i] = 0; // 색깔 모두 다 초기화
		}
 
		/* 간선과 정점 입력. */
		for (int i = 0; i < e; i++)
		{
			int a, b; // 두 정점 a,b
			cin >> a >> b;
 
			arr[a].push_back(b);
			arr[b].push_back(a);
		}
 
		/* 오름차순 정렬 */
		for (int i = 1; i <= v; i++)
		{
			sort(arr[i].begin(), arr[i].end());
		}
 
		/* dfs를 통해 해당 컬러(번호) 부여해주기 */
		for (int i = 1; i <= v; i++)
		{
			if (color[i] == 0)
			{
				dfs(i, 1);
			}
		}
 
		/* 이분그래프인지 아닌지 확인 */
		bool ok = true;
		for (int i = 1; i <= v; i++)
		{
			for (int k = 0; k < arr[i].size(); k++)
			{
				int j = arr[i][k]; // 연결된 노드
				if (color[i] == color[j]) // 연결된 정점이 같은 색깔이면 안됨.
				{
					ok = false;
				}
			}
		}
 
 
		if (ok)
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';
		}
 
 
	}
 
 
	return 0; // return 0 내부에 넣으면 끝나요... 밖에다 놓기.. ^_^
}

[ 코드 2 ]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
vector <int> arr[20001]; // 간선 v의 최대값은 20000이기 때문 (index 제외하고 20001개)
int color[20001]; // 0은 아직 접근 안한 것, 1/2는 색깔구분
// 이 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록 2가지 색깔로 칠해주는 것 
// 처음 노드를 선택했을 때 1, 1로 칠해진 노드의 다음 노드를 선택했을 때 2 .. (반복)
 
bool dfs(int node, int c) {
	color[node] = c; // true, false로 사용하고 안한것을 나눠주는 대신, 해당되는 번호(색깔)을 지정
 
	for (int i = 0; i < arr[node].size(); i++)
	{
		int next = arr[node][i];
		if (color[next] == 0) // 아직 color를 지정하지 않았다면
		{
			if (dfs(next, 3 - c) == false) // 다음 노드가 false를 반환했다면?
			{
				return false; // false를 계속 반환해라
			}
		}
		else if (color[next] == color[node]) // color를 지정했는데, 연결된 노드가 현재 노드와 같은 팀이라면?
		{
			return false; // 잘못된 결과 (false를 반환)
		}
	}
	return true; // 위의 조건에 다 충족한다면?
 
}
 
int main() {
	int k; // k : 테스트케이스 개수
	cin >> k;
 
	while (k--)
	{
		int v, e; // v : 정점의 개수, e : 간선의 개수
		cin >> v >> e;
 
		/* 초기화 */
		for (int i = 1; i <= v; i++)
		{
			arr[i].clear(); // 인접리스트 (vector) 초기화
			color[i] = 0; // 색깔 모두 다 초기화
		}
 
		/* 간선과 정점 입력. */
		for (int i = 0; i < e; i++)
		{
			int a, b; // 두 정점 a,b
			cin >> a >> b;
 
			arr[a].push_back(b);
			arr[b].push_back(a);
		}
 
		/* 오름차순 정렬 */
		for (int i = 1; i <= v; i++)
		{
			sort(arr[i].begin(), arr[i].end());
		}
 
		bool ok = true;
		for (int i = 1; i <= v; i++)
		{
			if (color[i] == 0)
			{
				if (dfs(i,1) == false) // 만약 반환이 false로 됐다면?
				{
					ok = false;
				}
			}
		}
 
 
		if (ok)
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';
		}
 
 
	}
 
 
	return 0; // return 0 내부에 넣으면 끝나요... 밖에다 놓기.. ^_^
}