백준 - 1707번 이분 그래프

문제

그래프의 정점의 집합을 둘로 분할하여,
각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할 할 수 있을 때,
이런 그래프를 이분 그래프라 부른다

그래프가 주어질 때, 이분 그래프인지 아닌지 판별해라!

생각

문제만 보고는 이분 그래프가 뭔지 잘 이해 못 했는데
이분 그래프 검색하고 이미지 보니까 바로 알았다

한 엣지에 이어져있는 노드끼리 다른 색으로 칠할 수 있어야 하는 느낌

아이디어 1

아직 탐색하지 않은 점은 0을 저장하고 있다가,
한 점을 1로 만들고 큐에 넣어서 탐색하면서 -1, 1, -1, 1 ...로 값을 저장

처음 방문한 노드에는 1인 노드에서 왔으면 -1을, -1인 노드에서 왔으면 1을 값으로 넣어주고

값이 있는 노드, 즉 다른 노드에 의해 -1이나 1이 저장되어있는 애를 만나면
지금 보고 있는 노드와 같은 값을 가지고 있는지 보고,
같다면 이분그래프가 아니라는 것을 알 수 있다!

int isBipartiteGraph(int check[], vector<int> info[], queue<int> q) {
	q.push(1);
	check[1] = 1;

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

		for (int i = 0; i < info[nowNode].size(); i++) {
			int nextNode = info[nowNode][i];
			if (check[nextNode] == 0) {
				q.push(nextNode);
				check[nextNode] = -1 * check[nowNode];
			}
			else {
				if (check[nextNode] == check[nowNode]) {
					return 0;
				}
			}
		}
	}
	return 1;
}

아이디어 2

완벽한 논리인데 틀렸습니다 가 나오더라
구글링하니까 아래와 같은 걸 신경써줘야했다

1. 모든 노드들이 다 한 그룹으로 연결되어있지 않을 수 있다!!
   그냥 그래프라고만 나와있으면 다 하나로 연결되어있다고 생각하지말구
   노드와 엣지가 아무렇게나 주어진 상황을 기본으로 생각해야한다고 한당
   (나는 기존에 점 1에서만 탐색을 시작했음)

2. 테스트 케이스가 새로 들어올 때 check, info배열, 심지어 큐까지 다 초기화 해줘야한다
   (나는 탐색중에 이분 그래프가 불가능하다고 알게되면
   바로 while 문을 탈출하기 때문에 큐에 값이 남아있을 수 있었따)

3. for문으로 방문한적 없는 노드에서 탐색을 시작하도록 함

4. 메인 함수 지역 변수로 배열과 큐를 만들어줌

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int k, n, e;
int tempa, tempb;

//모든 그래프들이 붙어있다는 전제가 없으니까, 1에서만 시작하면 안 돼 
bool isBipartiteGraph(int index, int check[], vector<int> info[]) {
	queue<int> q;
	q.push(index);
	check[index] = 1;

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

		for (int i = 0; i < info[nowNode].size(); i++) {
			int nextNode = info[nowNode][i];
			if (!check[nextNode]) {
				q.push(nextNode);
				check[nextNode] = -check[nowNode];
			}
			else if (check[nextNode] == check[nowNode]) {
				return false;
			}
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> k;

	for (int i = 0; i < k; i++) {
		cin >> n >> e;

		vector<int> info[20005];
		for (int j = 0; j < e; j++) {
			cin >> tempa >> tempb;
			info[tempa].push_back(tempb);
			info[tempb].push_back(tempa);
		}

		int check[20005] = { 0, };
		bool flag = true;
		for (int j = 1; j <= n && flag; j++) {
			if (check[j] == 0) {
				if (!isBipartiteGraph(j, check, info)) {
					flag = false;
				}
			}
		}

		if (flag) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}

	return 0;
}