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

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

 

 

💡문제 아이디어

이분그래프 판별 문제.

같은 그룹(색깔)끼리는 이어져 있으면 안된다.

탐색하면서 빈 노드가 있으면 다른 색깔로 칠하고, 같은 색깔이었으면 이분그래프 조건이 아니므로 0을 return한다

 

 

 

💡문제 코드

// 백준 1707 이분 그래프
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int K, V, E;
vector <int> alis[20001];
int visited[20001];

// 테스트케이스 전 그래프 초기화
void init() {
	memset(alis, 0, sizeof(alis));
	memset(visited, 0, sizeof(visited));
}

// 테스트케이스 당 그래프 생성
void input() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int from, to;
		cin >> from >> to;
		alis[from].push_back(to);
		alis[to].push_back(from);
	}
}

// DFS로 풀이 - 하나를 돌면 다른 그룹으로 설정 
int dfs(int nowNode, int colorNum) {

	visited[nowNode] = colorNum;

	int size = alis[nowNode].size();
		for (int i = 0; i < size; i++) {
		// 다음 노드가 같은 색깔, 이분그래프 불가
		int target = alis[nowNode][i];
		if (visited[target] == colorNum) {
			return 0;
		}
		// 다음 노드가 다른 색깔이었다면 그냥 지나가기
		else if (visited[target] == -colorNum) {
			continue;
		}
		// 비어있는 노드였다면 다른 색깔로 칠하기  
		else {
			int ret = dfs(target, -colorNum);
			if (ret == 0) return 0;	// dfs로 타고 올라온 결과가 0이면 0
		}
	}
	return 1;
}

int main() {
	//freopen("sample_input.txt", "r", stdin);

	cin >> K;
	for (int i = 0; i < K; i++) {
		init();
		input();

		// dfs 타서 해당 테스트케이스가 이분그래프인지 분별
		// 모든 node가 연결되지 않을 수 있을 수 있기 때문에, 모든 노드에 대해 테스트한다.
		int flag = 1;
		for (int i = 1; i <= V; i++) {

			if (!visited[i]) {
				int dfsResult = dfs(i, 1);
				if (dfsResult == 0) {
					flag = 0;
					break;
				}
			}
		}

		// 출력하기 
		if (flag == 1) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

 

 

💡메모리풀 이용

참고 블로그: https://bloodstrawberry.tistory.com/30

// 백준 1707 이분 그래프 - 메모리풀 이용
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int K, V, E;

struct NODE {
	int node;
	struct NODE* next;	// NODE형 구조체를 가리키는 포인터
};

// 전역변수로 메모리 미리 선언, 메모리 위치 나타내는 index
NODE HEAD[20001];	
NODE POOL[200001 * 2];	// 그래프 edge들 정보를 담을 곳 
int visited[20001];

int pcnt;

// 테스트케이스 전 그래프 초기화
void init() {
	pcnt = 0;	// 메모리 풀 초기화
	for (int i = 1; i <= V; i++) HEAD[i].next = 0;
	memset(visited, 0, sizeof(visited));
}

void makeEdge(int from, int to) {
	NODE* nd = &POOL[pcnt++];
	nd->node = to;
	nd->next = HEAD[from].next;
	HEAD[from].next = nd;
}

// 테스트케이스 당 그래프 생성
void input() {
	cin >> V >> E;
	for (register int i = 0; i < E; i++) {
		int from, to;
		cin >> from >> to;
		makeEdge(from, to);
		makeEdge(to, from);
	}
}

// DFS로 풀이 - 하나를 돌면 다른 그룹으로 설정 
int dfs(int nowNode, int colorNum) {

	visited[nowNode] = colorNum;

	for (NODE* p = HEAD[nowNode].next; p; p=p->next) {
		// 다음 노드가 같은 색깔, 이분그래프 불가
		if (visited[p->node] == colorNum) {
			return 0;
		}
		// 다음 노드가 다른 색깔이었다면 그냥 지나가기
		else if (visited[p->node] == -colorNum) {
			continue;
		}
		// 비어있는 노드였다면 다른 색깔로 칠하기  
		else {
			int ret = dfs(p->node, -colorNum);
			if (ret == 0) return 0;	// dfs로 타고 올라온 결과가 0이면 0
		}
	}
	return 1;
}

int main() {
	//freopen("sample_input.txt", "r", stdin);

	cin >> K;
	for (int i = 0; i < K; i++) {
		init();
		input();

		// dfs 타서 해당 테스트케이스가 이분그래프인지 분별
		// 모든 node가 연결되지 않을 수 있을 수 있기 때문에, 모든 노드에 대해 테스트한다.
		int flag = 1;
		for (int i = 1; i <= V; i++) {

			if (!visited[i]) {
				int dfsResult = dfs(i, 1);
				if (dfsResult == 0) {
					flag = 0;
					break;
				}
			}
		}

		// 출력하기 
		if (flag == 1) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}