백준(BOJ) 1707번 이분 그래프
문제 : https://www.acmicpc.net/problem/1707
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
나의 풀이:
이분 그래프가 되려면 DFS를 했을 시 현재 노드가 0 이라면 인접한 노드들은 1이여야 한다. 따라서 biGraph 배열을 추가로 하나 만들어서
한 노드의 인접한 노드들은 1 - (현재노드의 Bi값) 로 정의해줌으로써 현재 노드의 biGraph 값이 0 이라면 인접한 노드들은1을 1이라면 0을 반환하도록 해
주자
기존 DFS와 동일한 알고리즘에 biGraph 배열만 추가가 되고 답을 비교시에는 biGraph를 이용한다.
코드 ( C ++ )
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 20000 + 1;
vector<vector<int>> adj;
vector<bool> visited;
// 이분 그래프를 판단하는 배열 Bigraph
int Bigraph[MAX];
int V, E;
void DFS(int here, int binumber)
{
visited[here] = true;
// 현재 정점에 Bigraph값은 0아니면 1
Bigraph[here] = binumber;
for (int i = 0; i < adj[here].size(); ++i)
{
int there = adj[here][i];
if (!visited[there])
// 인접한 정점에 Bigraph 값은 0이면 1 , 1이면 0
DFS(there, 1 - binumber);
}
}
bool check()
{
for (int i = 1; i <= V; ++i)
{
int here = i;
for (int j = 0; j < adj[i].size(); ++j) {
int there = adj[i][j];
// 현재 정점과 인접한 정점이 같은 Bigraph를 가지면 false후 종료한다.
if (Bigraph[here] == Bigraph[there])
return false;
}
}
return true;
}
int main()
{
int C;
cin >> C;
while (C--) {
cin >> V >> E;
// 초기화
adj = vector<vector<int>>(MAX, vector<int>());
visited = vector<bool>(MAX, false);
memset(Bigraph, 0, sizeof(Bigraph));
for (int i = 0; i < E; ++i) {
int n1, n2;
cin >> n1 >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
for (int i = 1; i <= V; ++i)
if(!visited[i])
DFS(i, 1);
if (check())
cout << "YES" << "\n";
else
cout << "NO" << "\n";
}
return 0;
}
