[백준/c++] 1707번 - 이분 그래프

[ 문제 ]

 

 

 

 

[ 구현 ]

 

이분 그래프라면 연결된 간선의 양 끝점이 다른 색깔로 색칠될 수 있어야 한다라는 성질을 이용하면 쉽게 풀 수 있는 문제였다.

 

주어진 간선정보를 벡터에 채워넣어 그래프를 만들어 두고

그 그래프를 bfs로 탐색하면서 방문하지 않은 모든 점들에 대해 현재 점과는 다른 색으로 값을 채워넣어주는 식으로 구현하였다.

 

이렇게 구현한 bfs를 돌리고나면

결과적으로 간선이 연결된 모든 점들에 대해 어느 색깔이 칠해진 상태로 bfs 탐색이 마무리 될 것이고,

따라서 이후에는 전체 그래프를 탐색하면서 간선상의 두 점의 색이 다른지 아닌지 확인해주면 된다.

두 점의 색이 같은 경우 이분 그래프가 아니므로 바로 탈출이 가능하다.

 

 

 

 

[ 코드 ]

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int k, v, e;
vector<int> graph[20001];//연결된 간선 정보를 저장하는 벡터
int visited[20001];//1이면 red, 2이면 blue

void bfs(int idx) {
	queue<int> q;
	q.push(idx);
	visited[idx] = 1;//시작점을 red로

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

		for (int i = 0; i < graph[x].size(); i++) {
			int nx = graph[x][i];

			if(!visited[nx]) {
				if (visited[x] == 1) {
					visited[nx] = 2;
				}

				else if (visited[x] == 2) {
					visited[nx] = 1;
				}

				q.push(nx);
			}
		}
	}
}

bool check() {
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			if (visited[i] == visited[graph[i][j]])
				return false;
		}
	}
	return true;
}

int main() {
	cin >> k;
	while (k--) {
		cin >> v >> e;
		int a, b;

		while (e--) {
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		for (int i = 1; i <= v; i++) {
			if (!visited[i])
				bfs(i);
		}

		if (check()) 
			cout << "YES" << '\n';
		else 
			cout << "NO" << '\n';

		memset(graph, 0, sizeof(graph));
		memset(visited, 0, sizeof(visited));
	}

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

이분 그래프의 성질을 모르면 조금 접근하기 힘든 문제라고 느꼈다.

그래프 쪽 문제들은 이론을 알면 풀고 모르면 못 푸는 경우가 좀 많은 것 같으니 조금씩이라도 다양하게 풀어보는게 중요할 듯 하다.