[백준/C++] 1707번: 이분 그래프

문제

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

---

문제 요약

이분 그래프란,

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

 

그래프가 입력으로 주어질 때, 이분 그래프인지 아닌지 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int k;

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> k;
	
	// 테스트 케이스 반복
	while (k--) {
		// 그래프 정보 입력
		vector<int> edges[20020];
	
		int v, e;
		cin >> v >> e;

		for (int i = 0; i < e; i++) {
			int u, v;
			cin >> u >> v;

			edges[u].push_back(v);
			edges[v].push_back(u);
		}

		bool flag = false;
		
		// 노드 색 정보 초기화 (-1은 아직 방문하지 않은 노드)
		int color[20020];

		for (int j = 1; j <= v; j++) {
			color[j] = -1;
		}

		// 비연결 그래프일 경우를 대비하여 모든 노드를 검사
		for (int i = 1; i <= v; i++) {

			// 이미 방문했으면 패스
			if (color[i] != -1) continue;
			color[i] = 0;

			// 해당 노드부터 BFS 시작
			queue<pair<int, int>> q;
			q.push(make_pair(i, 0));

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

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

					// 인접한 노드의 색깔이 같을 경우 -> 이분 그래프 X
					if (x_color == color[nx]) {
						flag = true;
						break;
					}

					// 이미 방문한 노드는 더 이상 탐색 X
					if (color[nx] != -1) continue;

					// 이전 노드 색과 비교해서 큐에 삽입
					if (x_color == 0) {
						color[nx] = 1;
						q.push(make_pair(nx, 1));
					}
					else {
						color[nx] = 0;
						q.push(make_pair(nx, 0));
					}
				}
				if (flag) break;
			}
			if (flag) break;
		}

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

	}

	return 0;
}

---

코드 설명

테스트 케이스마다 그래프 정보를 입력 받고, 각 정점을 잡아 BFS을 진행한다.

 

탐색을 진행하면서, 자신과 인접한 노드 중 색이 같은 노드가 있다면, NO를 출력한다.

 

그렇지 않다면, YES를 출력한다.

---

고찰

1. 입출력 양이 많으므로, 입출력 단축 코드를 사용한다.

2. 비연결 그래프임을 고려하여 모든 노드에 방문했는지를 체크해야 한다.

 

3. 인접한 노드 중 이전에 방문했던 노드는 다시 큐에 넣지 않도록 주의한다.