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

문제

[C++] 백준 1707: 이분 그래프 GOLD 4
https://www.acmicpc.net/problem/1707

 

---

 

접근 방법

이 문제는 주어진 그래프가 이분 그래프인지 판별하는 문제이다.
이분 그래프란, 정점을 두 개의 집합으로 나누었을 때 같은 집합 내에서는 간선이 존재하지 않는 그래프를 의미한다.

이를 해결하기 위해 그래프를 탐색하면서 각 정점을 두 가지 색(0, 1)으로 칠하는 방식을 사용한다.

• 인접한 두 정점은 반드시 서로 다른 색이어야 함
• 만약 같은 색이 되면 → 이분 그래프 아님

그래프는 여러 개의 연결 요소로 나뉠 수 있으므로, 모든 정점을 시작점으로 탐색을 수행해야 한다.

탐색 방법은 DFS를 사용하였다.

 

상세 아이디어

1. 그래프 구성

vector<vector<int>> graph;

 

• 인접 리스트 형태로 그래프를 구성
• 양방향 그래프이므로 양쪽에 모두 간선 추가

 

 

2. 색(집합) 표현

vector<int> check;

 

• check[x] = 0 또는 1
• 서로 다른 집합을 의미

 

 

3. DFS 탐색 및 색칠

check[next] = (check[node] + 1) % 2;

이 부분이 핵심이다.

• 현재 노드가 0이면 → 다음 노드는 1
• 현재 노드가 1이면 → 다음 노드는 0

즉, 인접 노드를 항상 반대 집합으로 배치한다.

 

4. 이분 그래프 조건 검사

else if (check[node] == check[next])
    ret = false;

이미 방문한 노드인데 색이 같다면

• 같은 집합끼리 연결된 것이므로
• 이분 그래프 조건 위반

 

5. 모든 정점에서 DFS 수행

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

그래프가 하나로 이어져 있다는 보장이 없기 때문에 연결 요소별로 DFS를 수행해야 한다.

 

6. 결과 판단

 

• 한 번이라도 조건 위반 발생 → NO
• 끝까지 문제 없으면 → YES

 

 

구현 시 주의할 점

• 그래프가 여러 연결 요소로 나뉠 수 있으므로 모든 정점에서 DFS 시작 여부를 확인해야 한다.
• 인접 노드는 반드시 반대 집합으로 색칠해야 하며 (check[node] + 1) % 2 연산을 사용한다.
• 이미 방문한 노드라도 같은 색이라면 이분 그래프가 아니므로 즉시 종료해야 한다.
• visited는 방문 여부, check는 집합(색) 정보로 서로 다른 역할을 구분해서 사용해야 한다.
• 테스트케이스마다 assign을 사용하여 그래프와 배열을 완전히 초기화해야 한다.
• 이분 그래프가 아닌 것이 확인되면 불필요한 탐색을 줄이기 위해 즉시 반복문을 종료한다.

 

 

---

 

코드

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

vector<vector<int>> graph;
vector<bool> visited;
vector<int> check;
bool ret;

void DFS(int node)
{
	visited[node] = true;

	for (int i = 0; i < graph[node].size(); i++)
	{
		int next = graph[node][i];
		
		if (!visited[next])
		{
			check[next] = (check[node] + 1) % 2;
			// 이미 방문한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리
			DFS(next);
		}
		else if (check[node] == check[next])
			ret = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case = 0;
	cin >> test_case;
	for (int t = 0; t < test_case; t++)
	{
		int V = 0, E = 0;
		cin >> V >> E;

		graph.assign(V + 1, vector<int>());
		visited.assign(V + 1, false);
		check.assign(V + 1, 0);
		ret = true;

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

			graph[u].push_back(v);
			graph[v].push_back(u);
		}
		for (int i = 1; i <= V; i++)
		{
			// 그래프가 끊어져 있을 수 있기 때문에, 모든 정점에서 확인
			if (!visited[i])
				DFS(i);

			if (!ret)
				break;
		}
		if (ret)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
}