[백준/C++] 이분 그래프

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 정점들의 집합을 두 개로 분류했을 때, 집합 내에 속한 정점들이 서로 인접하지 않게 할 수 있는지 판단하는 문제다.

 

어떻게 하면 문제를 풀 수 있을지 한번 그림으로 생각해보자

먼저 위의 왼쪽 그림의 경우를 살펴보자

 

하나의 정점이 속할 집합이 정해지면, 인접한 정점은 다른 집합에 속해야 한다.

그러므로 이를 이용해 하나의 정점이 0번 집합에 속했다면, 인접한 정점은 전부 1번 집합에 넣는다.

 

마찬가지로 하나의 정점이 1번 집합에 속했다면, 인접한 정점은 전부 0번 집합에 넣으면 된다.

 

이렇게 정점들의 집합을 두개로 나눠서 채워 넣으면 한 집합에 속해있는 정점들은 서로 인접하지 않도록 만들 수 있다.

 

그런데 오른쪽 그림의 그래프는 문제가 있다.

 

인접한 정점이 다른 집합에 속해있게 하려고 했지만, ?의 부분에 어떤 집합이 와도 인접한 정점과 같은 집합에 속할 수 밖에 없게 된다.

 

그러므로 이 경우는 불가능한 경우다.

 

이렇게 그래프의 정점들이 속할 집합을 선택하면 되는데, 탐색해 나가는 과정을 queue를 이용해 BFS로 칸을 채우도록 했다.

 

 

 

​

[아이디어 정리]

1. 방문한 적이 없는 그래프의 임의의 정점을 정하고 0번 집합에 넣는다.
2. 0번 집합에 새로 넣은 정점과 인접한 정점은 모두 1번 집합에 넣는다.
3. 만약 인접한 정점이 이미 속해져 있는 집합이 정해져 있다면, 정해져 있는 집합이 현재 선택되는 집합과 같은지 비교한다.
4. 만약 같다면 계속 진행하고, 다르다면 함수를 종료해 NO를 출력한다.
5. 모든 정점의 집합이 정해질 때 까지 위 과정을 반복한다.

 

 

 

Code

 

 

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

void calc() 
{
	int V, E;
	cin >> V >> E;
	vector<vector<int>> graph(V + 1);
	int u, v;
	vector<int> visited(V + 1, 2); //2은 아직 선택 X, 0집합, 1집합;
	for (int i = 0; i < E; i++)
	{
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	int num;
	for (int i = 1; i <= V; i++)
	{
		if (visited[i] == 2)
		{
			queue<int> q;
			q.push(i);
			visited[i] = 0;
			while (!q.empty())
			{
				num = q.front();
				q.pop();
				for (int j = 0; j < graph[num].size(); j++)
				{
					if (visited[graph[num][j]] == 2)
					{
						visited[graph[num][j]] = (visited[num] + 1) % 2;
						q.push(graph[num][j]);
					}
					else
					{
						if (visited[graph[num][j]] == visited[num]) //인접해 있다면,
						{
							cout << "NO\n";
							return;
						}
					}
				}
			}
		}
	}
	cout << "YES\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int TC;
	cin >> TC;
	for (int tc = 0; tc < TC; tc++) 
	{
		calc();
	}
	
	return 0;
}

 

---

인접한 정점이 무조건 현재 정점과 다른 집합에 속해야된다는 점만 파악하면 쉽게 풀 수 있는 문제다.

 

1707번: 이분 그래프