[백준] 알고리즘 1707번 - 이분 그래프 문제

#include<iostream>
#include<algorithm>
#include<vector>
#include<memory.h>
using namespace std;
vector<int> v1[20001];
int check[20001];
void dfs(int x) {
	int size = v1[x].size();
	for (int i = 0; i < size; i++) {
		if (check[v1[x][i]] == 0) {
			if (check[x] == 1) {
				check[v1[x][i]] = 2;
			}
			else {
				check[v1[x][i]] = 1;
			}
			dfs(v1[x][i]);
		}
	} 
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		int v, e;
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			int x, y;
			cin >> x >> y;
			v1[x].push_back(y);
			v1[y].push_back(x);
		}
		for (int i = 1; i <= v; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				dfs(i);
			}
		}
		bool flag = true;
		for (int i = 1; i <= v; i++) {
			for (int j = 0; j < v1[i].size(); j++) {
				if (check[i] == check[v1[i][j]]) {
					flag = false;
					break;
				}
			}
		}
		if (flag == true) cout << "YES" << "\n";
		else cout << "NO" << "\n";
		for (int i = 1; i <= v; i++) {
			v1[i].clear();
			check[i] = 0;
		}
	}
}

구현방식

1. 상대 노드가 방문을 안했으면?? 즉 check[v1[x][i]](상대 노드)
if( 현재 자기자신의 노드색깔(check[x])가 1이면 상대 노드를 2로 바꿔준다. )
else ( 자기자신의 노드색깔이 2이면 상대 노드를 1로 바꿔준다.)
2. dfs(상대 노드) -> 만약 상대 노드를 방문했을 시 무시한다.

구현방식부분만 이해한다면, 해결할 수 있습니다.

저도 한참 고민하다 풀었네요

DFS, BFS 문제는 꾸준함이 필요한거 같습니다.