백준 1707. 이분 그래프

알고리즘 기초 문제 중 600 - 그래프 1 문제

이분 그래프

그래프 문제들은 포스팅할게 없어서 안하고 있었는데, 이 문제는 좋은 문제라 생각해서 올림

1. 간단 설명

이분 그래프인지 탐색하는 문제

일단 이분 그래프가 뭔지 이해하는게 중요하다

간단히 설명하면 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프

로 정의할 수 있다

이분 그래프에 대한 특징들은 별도로 다룰예정

2. 예시

• 첫번째 예시

  1 - 3 - 2
  

  1을 빨간색, 3을 파란색, 2를 빨간색으로 칠할 수 있으므로 이분 그래프이다

• 두번째 예시

1 - 2 - 3
    └ 4 ┛

1을 빨간색, 2를 파란색, 3을 빨간색, 4를 파란색으로 칠해버리면

2와 4가 인접한 정점이지만 둘 다 파란색이므로, 이분 그래프가 아니다

3. 알고리즘

이분 그래프를 판별하는 방법은

DFS 혹은 BFS를 이용해 모든 정점을 탐색하면서 색을 칠해보는 것이다

탐색을 하면서 이분 그래프인지 판별하는 방법과

모두 칠하고 나서 다시한번 확인하는 방법 두가지가 있는데

두가지 모두 진행해볼 예정

필요 변수

• 테스트케이스 개수 int K (2 ≤ K ≤ 5)
• 정점 개수 int V (1 ≤ V ≤ 20,000)

• 간선 개수 int E (1 ≤ E ≤ 200,000)

• 그래프 연결 정보를 저장할 2차원 벡터 vector< vector<int> > graph
• 노드 방문 여부 및 색을 저장할 배열 int visited[20001]

4. 소스코드

먼저 모든 그래프를 색칠하면서 탐색한뒤에

재 탐색으로 연속으로 칠이 된 곳을 찾는 방법

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int K, V, E;
vector< vector<int> > graph;
int visited[20001]; // 노드 방문 여부

void DFS(int node, int num) {
	
	visited[node] = num; // 현재 노드를 num으로 칠한다

	for (int i = 0; i < graph[node].size(); i++) {
		int next = graph[node][i];
		
		// 방문하지 않은 노드라면 
		if (visited[next] == 0) {
			DFS(next, 3 - num); // 1이면 2를, 2라면 1을 매개변수로 넘겨줌
		}
	}

}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> K;
	while (K--) {
		cin >> V >> E;
		memset(visited, 0, sizeof(visited));
		graph.clear();
		graph.resize(V + 1);

		for (int i = 0; i < E; i++) {
			int start, end;
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start); // 양방향
		}

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

		bool result = true;

		// 모든 노드 탐색
		for (int i = 1; i <= V; i++) {
			for (int j = 0; j < graph[i].size(); j++) {
				int next = graph[i][j];
				if (visited[i] == visited[next]) {
					result = false;
					break;
				}
			}
			if (result == false) break;
		}

		if (result) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

칠하면서 동시에 연속으로 색칠된 곳을 찾는 방법

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int K, V, E;
vector< vector<int> > graph;
int visited[20001]; // 노드 방문 여부
bool result = true;

void DFS(int node, int num) {
	if (result == false) { return; }

	visited[node] = num;

	for (int i = 0; i < graph[node].size(); i++) {
		int next = graph[node][i];
		// 아직 방문 안한 경우
		if (visited[next] == 0) {
			DFS(next, 3-num);
		}

		// 방문했던 경우
		else {
			// 현재 노드와 다음 노드의 번호가 같다면 이분 그래프가 아님
			if (visited[next] == visited[node]) {
				result = false;
				return;
			}
		}
	}

}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> K;
	while (K--) {
		cin >> V >> E;
		result = true;
		memset(visited, 0, sizeof(visited));
		graph.clear();
		graph.resize(V + 1);

		for (int i = 0; i < E; i++) {
			int start, end;
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start); // 양방향
		}

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

		if (result) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}

문제 풀던 중에, DFS(int level, int num) 대신 전역 변수 toggle를 두어서 색을 toggle로 칠하는 방법을 사용했었다

즉 toggle을 DFS를 호출할때 마다 1, -1로 왔다갔다하면서 색을 칠하는 방법을 썼는데

이 방법은 DFS에서 문제가 발생했다

예를들어

1 - 2 - 3
|   |
4 - 5

와 같은 경우 1은 1, 2는 -1, 3은 1

5는 1을 칠해야하지만, -1을 칠해버리는 문제가 발생했다

이거 찾는데 시간 엄청 날려먹음

이분 그래프 체크할때 DFS를 사용할꺼라면 매개변수로 색을 넘겨주는 방법을 사용하는걸로