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

 

1707번: 이분 그래프

 

이분 그래프 (Bipartite Graph) 의 개념을 알고있거나 문제에서 빠르게 이해했다면 그리 어렵지 않은 탐색 문제다.
하지만 문제의 설명이 짧고 친절하지도 않은 편이라 혼란스러울 수 있는 부분들이 있었다.

 

 

노골적으로 그래프 문제임을 보여주고있지만 자세한 설명이나 예시 없이 이분 그래프인지 아닌지를 판별하도록 하고있다.

이분 그래프라는 개념을 어느정도 알고 있었다면 그나마 접근이 용이하겠지만 그렇지 않은 경우 예시도 없는 한줄 설명 만으로 빠르고 정확히 이해하기에는 쉽지 않은 편이었다.

 

 

문제 자체에서 여러번 탐색이 필요하다거나 특정 알고리즘을 사용한다거나 구현 양이 많아지는 문제는 아니지만 생소할 수 있는 문제라 한번쯤 풀어보면 좋을 문제다.

 

 

---

 

 

문제의 포인트

이분 그래프의 개념
이분 그래프 확인 방법

 

 

이분 그래프의 개념

이분 그래프 (Bipartite Graph), 출처 - Wikipedia

 

 

 

사실 문제에서의 설명이 짧지만 정확한 편이다.

다만 그래프의 정점의 집합에 대해서는 알고리즘 문제를 풀면서 접하기 쉽지 않은 개념이다 보니 한번에 와닿지 않는 것 같다.

 

 

쉽게 말해 서로 연결되지 않은 노드들끼리 그룹을 지어서 정확히 둘로 나눌 수 있는 그래프라면 이분 그래프 (Bipartite Graph)가 된다.

이를 쉽게 표현하기 위해 노드에 색을 칠한다는 개념을 이용해서 인접한 (연결되어있는) 노드끼리는 서로 다른 색을 칠할 때 두가지 색으로만 모든 노드를 칠할 수 있는 그래프로 설명하기도 한다.

 

 

이분 그래프 확인 방법

 

 

 

만약 프로그램이 아닌 사람이 이분 그래프인지 아닌지 확인한다면 어떻게 접근하면 좋을까?

위에서 색을 이용해서 설명한 것과 같이 색을 칠하면서 모든 노드를 탐색해보면 쉽게 확인할 수 있다.

 

 

시작점부터 연결된 노드들에는 색을 바꿔가면서 칠하되 두가지 색으로만 번갈아 가면서 칠해보면, 이분 그래프일 때 문제없이 모든 노드에 색을 칠할 수 있을 것이다.

이분 그래프가 아니라면 어느 순간 인접한 노드들이 같은 색으로 칠해질 수 밖에 없는 상황이 발생한다.

 

 

이와 같이 간단히 각 노드의 번호를 index로 갖는 배열을 이용해 칠한 색을 기록하면서 탐색을 마치고 인접한 노드끼리 같은 색이 칠해진 case가 있는지 확인하면 된다.

각 노드별로 인접한 노드를 리스트로 연결한 인접 리스트 (Adjacency List)를 이용하면 이 역시 어렵지 않게 찾을 수 있다.

 

 

---

 

전체 Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int K, V, E;
vector<int> adj[20000 + 10];
queue<int> q;
int check[20000 + 10];

void initGraph() {
	int i;
	for (i = 1; i <= V; i++) {
		adj[i].clear();
		check[i] = 0;
	}
}

int checkAdj() {
	int i, j, group;

	for (i = 1; i <= V; i++) {
		group = check[i];
		for (j = 0; j < adj[i].size(); j++) {
			if (check[adj[i][j]] == group)
				return 0;
		}
	}	
	return 1;
}

void BFS(int n) {
	int curr, i, next;

	check[n] = 1;
	q.push(n);

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

		for (i = 0; i < adj[curr].size(); i++) {
			next = adj[curr][i];
			if (check[next] > 0) continue;

			q.push(next);
			if (check[curr] == 1)
				check[next] = 2;
			else if (check[curr] == 2)
				check[next] = 1;			
		}
	}
}

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

	int t, i, a, b;

	cin >> K;

	for (t = 0; t < K; t++) {
		cin >> V >> E;
		initGraph();

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

		for (i = 0; i < V; i++) {
			if (check[i] == 0)
				BFS(i);
		}

		if (checkAdj())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}