본문 바로가기
알고리즘/그래프

그래프의 표현 - 이분 그래프 판별하기

by sim0609 2023. 3. 11.

이 문제는 이분 그래프에 대한 기초 지식을 요구한다.
 
이분 그래프란 아래 그림처럼 모든 꼭짓점을 빨강색(집합1)과 파랑색(집합2)으로 표현하되, 모든 변이 빨강색(집합1)과 파랑색(집합2) 꼭짓점을 포함하도록 표현되는 그래프이다. 이 말은 즉, 그래프에서 사이클이 존재하면 안된다는 의미이다.

 

 

<문제>

백준 - 1707: 이분 그래프 판별하기
https://www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

 

첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 따라서, K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력하는 문제이다. 

 
 

예)
입력             출력
2                  YES
3 2               NO
1 3
2 3
4 4
1 2
2 3
3 4
4 2
 

<문제 해결>

1. 이분 그래프를 체크해주는 변수와 각 노드의 집합을 표현(현재 노드와 이전 노드를 다른 집합으로 처리)해주는 벡터 변수가 필요하다.
 
2. 주어진 그래프를 모두 방문하지 않을 수도 있기 때문에 main 함수에서 각 노드를 모두 방문하는 코드를 추가해야 한다.
 
3. 여러개의 testcase에 대비해 기존에 사용했던 노드를 저장하는 graph 2차원 벡터, 노드 방문 여부를 나타내는 visited 벡터, 각 노드의 집합을 표현하는 check 벡터를 모두 초기화해줘야 한다.
 

Considerations)

testcase에 대한 초기화 진행할 때, visited.resize(n_num + 1, 0), check.resize(n_num + 1, 0)로 초기화하면 안된다. 왜냐하면, 나중 벡터 visited, check가 기존 벡터보다 크기가 작으면 resize로 값 할당이 안되기 때문이다.
 

Approach 1. BFS - queue 이용

<슈도 코드>

testcase = 테스트 케이스 개수
n_num = 노드 개수
e_num = 간선 개수
n1 = 노드1
n2 = 노드2
check = 각 노드별 해당 집합 표현
b = 이분 그래프 여부

int main() {

	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		cin >> n_num >> e_num;
		graph.resize(n_num + 1);
		visited.resize(n_num + 1);
		check.resize(n_num + 1);
		b = 1; // 이진 그래프인 경우: b = 1, 이진 그래프가 아닌 경우: b = 0

		for (int i = 0; i < e_num; i++) {
			cin >> n1 >> n2;
			graph[n1].push_back(n2);
			graph[n2].push_back(n1);
		}

		for (int i = 1; i <= n_num; i++) {
			if (b == 1) {
				BFS(i);
			}
			else {
				break;
			}
		}

		if (b == 1) {
			//b_contain.push_back(1);
			cout << "YES" << endl;
		}
		else {
			//b_contain.push_back(0);
			cout << "NO" << endl;
		}

		for (int i = 0; i <= n_num; i++) { // testcase 반복에 대비한 초기화
			graph[i].clear();
			visited[i] = 0;
			check[i] = 0;
		}
		//visited.resize(n_num + 1, 0);, check.resize(n_num + 1, 0);로 초기화하면 안됨 -> 나중 벡터가 기존보다 크기가 작으면 resize로 값 할당이 안됨
	}
}

void BFS(int n) {
	queue <int> q;

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

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

		for (int i = 0; i < graph[f].size(); i++) {
			if (visited[graph[f][i]] == 0) { // 방문하지 않은 노드에 이전 노드와 다른 숫자 그룹 표시해주기
				check[graph[f][i]] = (check[f] + 1) % 2;
				visited[graph[f][i]] = 1;
				q.push(graph[f][i]);
			}
			else if (check[graph[f][i]] == check[f]) { // 이미 방문한 노드가 현재 노드와 같은 그룹이면 이분 그래프가 아님
				b = 0;
				break;
			}
		}
	}
}

 

<전체 코드>

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

vector <vector<int>> graph;
vector <int> visited;
vector <int> check;
int b;

void BFS(int n);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase, n_num, e_num;
	int n1, n2;

	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		cin >> n_num >> e_num;
		graph.resize(n_num + 1);
		visited.resize(n_num + 1);
		check.resize(n_num + 1);
		b = 1; // 이진 그래프인 경우: b = 1, 이진 그래프가 아닌 경우: b = 0

		for (int i = 0; i < e_num; i++) {
			cin >> n1 >> n2;
			graph[n1].push_back(n2);
			graph[n2].push_back(n1);
		}

		for (int i = 1; i <= n_num; i++) {
			if (b == 1) {
				BFS(i);
			}
			else {
				break;
			}
		}

		if (b == 1) {
			//b_contain.push_back(1);
			cout << "YES" << endl;
		}
		else {
			//b_contain.push_back(0);
			cout << "NO" << endl;
		}

		for (int i = 0; i <= n_num; i++) { // testcase 반복에 대비한 초기화
			graph[i].clear();
			visited[i] = 0;
			check[i] = 0;
		}
		//visited.resize(n_num + 1, 0);, check.resize(n_num + 1, 0);로 초기화하면 안됨 -> 나중 벡터가 기존보다 크기가 작으면 resize로 값 할당이 안됨
	}
}

void BFS(int n) {
	queue <int> q;

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

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

		for (int i = 0; i < graph[f].size(); i++) {
			if (visited[graph[f][i]] == 0) { // 방문하지 않은 노드에 이전 노드와 다른 숫자 그룹 표시해주기
				check[graph[f][i]] = (check[f] + 1) % 2;
				visited[graph[f][i]] = 1;
				q.push(graph[f][i]);
			}
			else if (check[graph[f][i]] == check[f]) { // 이미 방문한 노드가 현재 노드와 같은 그룹이면 이분 그래프가 아님
				b = 0;
				break;
			}
		}
	}
}

 

Approach 2. DFS - 재귀 함수 이용

<슈도 코드>

testcase = 테스트 케이스 개수
n_num = 노드 개수
e_num = 간선 개수
n1 = 노드1
n2 = 노드2
check = 각 노드별 해당 집합 표현
b = 이분 그래프 여부

int main() {
	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		cin >> n_num >> e_num;
		graph.resize(n_num + 1);
		visited.resize(n_num + 1); 
		check.resize(n_num + 1); 
		b = 1; // 이분 그래프인 경우: b = 1, 이분 그래프가 아닌 경우: b = 0

		for (int i = 0; i < e_num; i++) {
			cin >> n1 >> n2;
			graph[n1].push_back(n2);
			graph[n2].push_back(n1);
		}

		for (int i = 1; i <= n_num; i++) {
			if (b == 1) {
				DFS(i);
			}
			else {
				break;
			}
		}

		if (b == 1) {
			//b_contain.push_back(1);
			cout << "YES" << endl;
		}
		else{
			//b_contain.push_back(0);
			cout << "NO" << endl;
		}

		for (int i = 0; i <= n_num; i++) { // testcase 반복에 대비한 초기화
			graph[i].clear(); 
			visited[i] = 0;
			check[i] = 0;
		}
		//visited.resize(n_num + 1, 0);, check.resize(n_num + 1, 0);로 초기화하면 안됨 -> 나중 벡터가 기존보다 크기가 작으면 resize로 값 할당이 안됨
	}
}

void DFS(int n) {
	visited[n] = 1;
	for (int i = 0; i < graph[n].size(); i++) {
		if (visited[graph[n][i]] == 0) { // 방문하지 않은 노드에 이전 노드와 다른 숫자 그룹 표시해주기
			check[graph[n][i]] = (check[n] + 1) % 2;
			DFS(graph[n][i]);
		}
		else if(check[graph[n][i]] == check[n]) { // 이미 방문한 노드가 현재 노드와 같은 그룹이면 이분 그래프가 아님
			b = 0;
			break;
		}
	}
}

 

<전체 코드>

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

vector <vector<int>> graph;
vector <int> visited;
vector <int> check;
int b;

void DFS(int n);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase, n_num, e_num;
	int n1, n2;

	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		cin >> n_num >> e_num;
		graph.resize(n_num + 1);
		visited.resize(n_num + 1); 
		check.resize(n_num + 1); 
		b = 1; // 이진 그래프인 경우: b = 1, 이진 그래프가 아닌 경우: b = 0

		for (int i = 0; i < e_num; i++) {
			cin >> n1 >> n2;
			graph[n1].push_back(n2);
			graph[n2].push_back(n1);
		}

		for (int i = 1; i <= n_num; i++) {
			if (b == 1) {
				DFS(i);
			}
			else {
				break;
			}
		}

		if (b == 1) {
			//b_contain.push_back(1);
			cout << "YES" << endl;
		}
		else{
			//b_contain.push_back(0);
			cout << "NO" << endl;
		}

		for (int i = 0; i <= n_num; i++) { // testcase 반복에 대비한 초기화
			graph[i].clear(); 
			visited[i] = 0;
			check[i] = 0;
		}
		//visited.resize(n_num + 1, 0);, check.resize(n_num + 1, 0);로 초기화하면 안됨 -> 나중 벡터가 기존보다 크기가 작으면 resize로 값 할당이 안됨
	}
}

void DFS(int n) {
	visited[n] = 1;
	for (int i = 0; i < graph[n].size(); i++) {
		if (visited[graph[n][i]] == 0) { // 방문하지 않은 노드에 이전 노드와 다른 숫자 그룹 표시해주기
			check[graph[n][i]] = (check[n] + 1) % 2;
			DFS(graph[n][i]);
		}
		else if(check[graph[n][i]] == check[n]) { // 이미 방문한 노드가 현재 노드와 같은 그룹이면 이분 그래프가 아님
			b = 0;
			break;
		}
	}
}

'알고리즘 > 그래프' 카테고리의 다른 글

그래프의 표현 - 물의 양 구하기  (0) 2023.03.11
그래프의 표현 - 효율적으로 해킹하기  (0) 2023.03.11
그래프의 표현 - 특정 거리의 도시 찾기  (0) 2023.03.11

관련글

티스토리툴바