[백준1707] 이분 그래프 (C++)

📌문제

BOJ 바로가기

정답률이 낮은 문제이다. 그도 그럴 것이 고려해줘야 할 부분이 정말 많다. 대표적으로 놓치기 쉬운 부분은 다음과 같이 두 가지가 있다.

1. 끊어진 그래프일 가능성 (연결 요소가 2개 이상)
2. 테스트케이스가 들어올 때마다 초기화

📌풀이

BFS를 이용해 노드를 먼저 칠해주고 마지막에 검사를 하는 함수를 만들었다. (물론 DFS로도 가능하다.)
처음에는 노드를 칠하는 동시에 앞의 노드와 색이 같으면 바로 false를 반환하는 로직을 생각했는데, 어떤 경우에서는 반례를 찾지 못하고 YES를 반환해버릴 가능성이 있다는 사실을 나중에 깨달았다. 역시 생소한 개념의 문제는 이 경우 저 경우 직접 해보면서 촘촘한 로직을 짜는 게 중요할 것 같다🥶

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int k, v, e;
vector<int> ilist[20001];
int group[20001]; // 방문 안했으면 0, 방문했고 그룹1이면 1, 방문했고 그룹2면 2를 표시하기 위한 배열
bool ans;

void bfs(int node)
{
	queue<int> q;
	group[node] = 1;
	q.push(node);
	while (!q.empty())
	{
		int temp = q.front();
		q.pop();
		for (int i = 0; i < ilist[temp].size(); i++)
		{
			int next = ilist[temp][i];
			if (group[next] == 0) // 방문하지 않았던 노드일 경우
			{
				group[next] = 3 - group[temp]; // 전 값이 1그룹이면 2그룹으로, 2그룹이면 1그룹으로 초기화
				q.push(next);
			}
		}
	}
}

// 인접한 두 노드가 같은 색이면 바로 false 반환!
bool is_okay()
{
	for (int i = 1; i <= v; i++)
	{
		for (int j = 0; j < ilist[i].size(); j++)
			if (group[i] == group[ilist[i][j]])
				return false;
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> k;
	while (k--)
	{
		cin >> v >> e;
		// 테스트케이스가 들어올 때마다 초기화
		ans = true;
		memset(group, 0, sizeof(group));
		for (int i = 1; i <= v; i++)
			ilist[i].clear();
		// 그래프 만들어주기
		for (int i = 0; i < e; i++)
		{
			int from, to;
			cin >> from >> to;
			ilist[from].push_back(to);
			ilist[to].push_back(from);
		}
		// 연결 요소가 두 개 이상일 가능성 고려(끊어진 그래프일 수도 있음)
		for (int i = 1; i <= v; i++)
		{
			if (group[i] == 0)
				bfs(i);
		}
		// 검사 후 결과 출력
		if (is_okay())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}