[알고리즘] 백준 1707번: 이분 그래프 (C++)

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

이분 매칭 알고리즘을 배우기 앞서 이분 그래프를 알아두면 좋을 거 같아 공부해보았다.

 

처음에는 BFS나 DFS로 어떻게 탐색해낼까 생각도 못 했다. (DFS나 BFS가 그래프 탐색 알고리즘이기 때문에)

솔루션을 참고했다. (https://jdselectron.tistory.com/51)

 

우선 이분 그래프를 보고, 이분 그래프의 특징 하나를 파악할 수 있어야 한다.

[문제에 있던 글]

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

즉, 이 말을 한 번 꼬아서 생각하면 인접한 정점끼리는 서로 다른 집합의 정점이다라는 특징을 파악할 수 있다.

 

그리고, 솔루션은

현재 노드와 연결된 다음 노드(nextNode)를 방문하면서 '현재 노드와는 다른 영역이다'를 다음 노드에게 알려주면 된다.

탐색이기 때문에 BFS를 활용하고, 영역은 색깔 ("RED" or "BLUE")를 통해 나타내 주었다.(문자열 배열 선언)

이분 그래프가 아니라면 인접한 노드끼리 같은 색깔이 되어있다.

[BFS]

void bfs(int node) {
	visited[node] = 1;
	color[node] = "RED";
	queue<int> q;
	q.push(node);
	while(!q.empty()) {
		int front = q.front();

		q.pop();
		for (int i = 0; i < graph[front].size(); i++) {
			int next = graph[front][i];
			if (!visited[next]) {
				visited[next] = 1;
				q.push(next);
				if (color[front] == "RED") {
					color[next] = "BLUE";
				}
				else if (color[front] == "BLUE") {
					color[next] = "RED";
				}
			}
		}
	}
}

 

정점을 돌며 인접한 노드가 같은 색인지 다른 색인지의 여부를 판단하는 함수가 필요하다.

bool isBipartiteGraph() {
	for (int i = 1; i <= v; i++) {
		int graphSize = graph[i].size();
		for (int j = 0; j < graphSize; j++) {
			int next = graph[i][j];
			if (color[i] == color[next]) {
				return 0;
			}
		}
	}
	return 1;
}

 

[AC 코드]

#include <iostream>
#include <queue>
#include <vector>
#define MAX 20000 + 1
using namespace std;

int T;
int v, e;
vector<int> graph[MAX];
bool visited[MAX];
string color[MAX];
vector<int> left, right;

void bfs(int node) {
	visited[node] = 1;
	color[node] = "RED";
	queue<int> q;
	q.push(node);
	while(!q.empty()) {
		int front = q.front();

		q.pop();
		for (int i = 0; i < graph[front].size(); i++) {
			int next = graph[front][i];
			if (!visited[next]) {
				visited[next] = 1;
				q.push(next);
				if (color[front] == "RED") {
					color[next] = "BLUE";
				}
				else if (color[front] == "BLUE") {
					color[next] = "RED";
				}
			}
		}
	}
}

bool isBipartiteGraph() {
	for (int i = 1; i <= v; i++) {
		int graphSize = graph[i].size();
		for (int j = 0; j < graphSize; j++) {
			int next = graph[i][j];
			if (color[i] == color[next]) {
				return 0;
			}
		}
	}
	return 1;
}

void init(int n) {
	for (int i = 1; i <= n; i++) {
		graph[i].clear();
		visited[i] = 0;
		color[i] = "";
	}
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> v >> e;

		init(v);

		for (int i = 0; i < e; i++) {
			int u, v;
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}

		for (int i = 1; i <= v; i++) {
			if (!visited[i]) {
				bfs(i);
			}
		}

		if (isBipartiteGraph()) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}
	}
	return 0;
}

---

이번 문제는 '이분 그래프'의 정의와 '문제를 한번 꼬아서 생각해보자 -> 반대로'의 접근 스킬을 키울 수 있었다.

업 솔빙하면 좋은 문제!