백준 1707 - 이분 그래프

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 주어진 그래프가 이분 그래프인지 판단하면 된다.

 

이분 그래프를 판단하는 방법은 간단하다.

임의의 노드를 시작으로 번갈아가며 표시하고 만약 표시된 노드를 다시 만났을 때 현재 표시해야 하는 것과 다르게 표시되어 있다면 이는 이분 그래프가 아닌 것이다.

예를 들어 보자.

위와 같은 그래프가 있다고 가정해 보자.

1번 노드를 시작으로 번갈아 가며 색을 칠해 보자.

그 다음 1번 노드와 인접한 노드인 3번 노드를 다른 색으로 칠한다.

마찬가지로 동일한 방법으로 2번 노드를 칠하면 다음과 같다. 

이는 정확히 이분 그래프가 된다.

 

다른 예시로 다음과 같은 그래프가 주어졌다고 가정해 보자.

동일하게 1번을 시작으로 색을 칠해 나간다.

이때 연결된 노드가 {2, 3}에 다른 색을 칠한다.

2번을 먼저 칠하고 2번과 연결된 3번을 칠하려 했더니 3번은 이미 2번과 동일한 색으로 칠해져 있다.

이는 명백히 이분 그래프가 아니다.

 

위와 같은 논리로 이분 그래프를 판단하려면 BFS를 활용하면 된다.

색을 칠하는 것을 방문 여부를 체크하는 로직으로 대체하면 된다.

q.push({ 1, 1 });

while (!q.empty())
{
	auto [current, flag] = q.front();
	q.pop();

	if (visited[current] == flag) continue;
	visited[current] = flag;

	auto nextFlag = flag == 1 ? 2 : 1;
	for (auto next : adj[current])
	{
		if (visited[next] == 0)
		{
			q.push({ next, nextFlag });
			continue;
		}

		if (visited[next] != nextFlag)
		{
			cout << "NO\n";
			bPossible = false;
			break;
		}
	}

	if (!bPossible) break;
}

 

단 한가지 주의할 점은 주어지는 그래프가 연결 그래프가 아닐 수 있다는 점이다.

따라서 모든 노드를 순회하며 방문하지 않은 노드를 시작으로 BFS를 진행해야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int T, V, E;
vector<vector<int>> adj;
vector<int> visited;

int main()
{
	INPUT_OPTIMIZE;

	cin >> T;

	while (T--)
	{
		cin >> V >> E;

		adj.clear();
		adj.resize(V + 1, vector<int>());

		visited.clear();
		visited.resize(V + 1, 0);

		for (int i = 0; i < E; i++)
		{
			int a, b;
			cin >> a >> b;
			
			adj[a].push_back(b);
			adj[b].push_back(a);
		}

		queue<pair<int,int>> q;
		bool bPossible = true;

		for (int i = 1; i <= V; i++)
		{
			if (!bPossible) break;
			if (visited[i] != 0) continue;

			q.push({ i, 1 });

			while (!q.empty())
			{
				auto [current, flag] = q.front();
				q.pop();

				if (visited[current] == flag) continue;
				visited[current] = flag;

				auto nextFlag = flag == 1 ? 2 : 1;
				for (auto next : adj[current])
				{
					if (visited[next] == 0)
					{
						q.push({ next, nextFlag });
						continue;
					}

					if (visited[next] != nextFlag)
					{
						cout << "NO\n";
						bPossible = false;
						break;
					}
				}

				if (!bPossible) break;
			}
		}

		if (bPossible) cout << "YES\n";
	}
	

	return 0;
}

---