[BOJ] 백준 1707번 : 이분 그래프 C++ : 아주정은

이문제는 생각이 많이 필요한 문제였다. 왜냐하면 문제 자체를 이해하지 못하였기 때문이다.

나는 이분그래프라고해서 그래프중에 트리를 말하는줄알고 처음에는 사이클이 존재하는지 여부를 따졌었다. 그래도 예제는 통과할 수 있었는데, 계속 틀렸다고 나와서 결국 구글에 검색을 하였다........꾸준함님의 블로그를 참조하였다.....

거의 카피했다고 봐도 무방;;;;; 그래도 마지막 자존심으로 변수이름이나....내가 쓰던 패턴들은 그대로 썻다;;; 이것까지 바꾸는건 좀 그랬다...

꾸준함님이 코드를 워낙 잘짜놔서 현타가 씨게 왔다;;

이분 그래프란 그래프에서 노드들을 두 집합으로 나눴을때 같은 집합에 있는 노드들끼리 연결된 것이 없을때 이분그래프라고 할 수 있다.

그래서 BFS든 DFS든 완전탐색을 통해서 모든 노드들을 탐색하면서 각각 노드들에 색깔을 입혀준다. 그 다음 모든 노드를 돌면서 각각의 노드에 연결된 이웃들이 자신과 색깔이 같은지 판단을 하면된다.

소스코드는 아래 첨부한다. 나중에 필히 다시 풀어볼 문제이다. 왜냐하면 어디선가 또 나올것같은 문제이기 때문이다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> board;
vector<int> vis; // 노드 방문여부 및 색깔

void DFS(int input, int color) {
	vis[input] = color;
	for (int i = 0; i < board[input].size(); i++) {
		if (vis[board[input][i]] == 0) {
			DFS(board[input][i], 3 - color);
		}
	}
}

bool is_disparity() {
	
	for (int i = 0; i < vis.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			if (vis[i] == vis[board[i][j]]) return false;
		}
	}
	return true;
}

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

	int K, V, E; // 케이스 갯수, 정점 갯수, 간선 갯수
	int a, b;
	cin >> K;

	while (K--) {
		cin >> V >> E;

		board.assign(V+1, vector<int>(0,0));// vector 초기화
		vis.assign(V+1, 0);
		
		while (E--) {
			cin >> a >> b;
			board[a].push_back(b);
			board[b].push_back(a);
		} // 그래프 그리기

		for (int i = 1; i < V + 1; i++) {
			if (vis[i] == 0) {
				DFS(i,1);
			}
		} // 컬러 다 입혔다.
		
		if (is_disparity()) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		
	}
}