[C/C++] 백준 1707번 - 이분 그래프 (Red-Black Tree)

 

문제

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

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

입력

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

출력

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

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int K, V, E;
int u, v;
int red_black_tree[20001]; // 0:방문x, 1:RED, 2:BLACK
bool ans;
vector<int> graph[20001];
vector<pair<int, int>> check;
queue<int> q;

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

	cin >> K;

	while (K--)
	{
		cin >> V >> E; // 정점과 간선 수

		
		check.clear(); // 간선 정보 초기화
		for (int i = 1; i <= V; i++) // 그래프, 레드-블랙 트리 초기화
		{
			red_black_tree[i] = 0;
			graph[i].clear();
		}
			

		for (int i = 0; i < E; i++)
		{
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
			check.push_back({ u,v }); // 간선 정보
		}

		// 레드-블랙 트리 만들기
		for (int i = 1; i <= V; i++)
		{
			if (red_black_tree[i] == 0) // 아직 방문하지 않은 노드일 때
			{
				red_black_tree[i] = 2; // 시작점을 BLACK 로
				q.push(i);
			}
				

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

				for (int j = 0; j < graph[node].size(); j++)
				{
					int next_node = graph[node][j];

					if (red_black_tree[next_node] == 0) // 아직 방문하지 않은 노드일 때
					{
						if (red_black_tree[node] == 1) // 현재 노드가 RED라면
							red_black_tree[next_node] = 2; // 다음 노드는 BLACK
						else if (red_black_tree[node] == 2) // 현재 노드가 BLACK라면
							red_black_tree[next_node] = 1; // 다음 노드는 RED
						q.push(next_node);
					}
				}
			}

		}

		// 이분그래프인지 체크
		ans = true;

		while (!check.empty())
		{
			int x = check.back().first;
			int y = check.back().second;
			check.pop_back();

			if (red_black_tree[x] == red_black_tree[y])
			{
				ans = false;
				break;
			}
		}


		cout << (ans ? "YES" : "NO") << '\n';
	}
}

 

풀이 방법

 

레드-블랙 트리

 

레드-블랙 트리의 개념을 이용하여 정점과 간선의 정보를 받아 BFS로 레드-블랙 트리를 만들고 간선들의 정보를 담은 check 벡터를 통해서 모든 간선들을 검사하여 하나의 간선으로 이어진 두 정점의 색이 같은 것이 존재하는지 판별한다. 색이 같은 것이 존재한다면 레드-블랙 트리가 아니므로 이분 그래브가 될 수없다.

 

간단한 예시를 들자면,

 

위의 그래프의 경우는 이분 그래프가 성립하지만,,,,,

아래의 그래프의 경우에는 3과 4가 간선으로 이어져있고 같은 색이므로 이분 그래프가 성립하지 않는다.

 

 

www.acmicpc.net/problem/1707

1707번: 이분 그래프