[BOJ] 백준 1707번 이분그래프 (C++ 코드)

🧨 백준 1707번 - 이분 그래프

문제 난이도 : 골드4 (낮은 정답률에는 이유가 있다)

문제 링크 : www.acmicpc.net/problem/1707

1707번: 이분 그래프

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

🧨 알고리즘 선택 및 C++ 코드

메모리초과, 런타임에러(Segfault, OutofBounds)에 틀렸습니다 에러까지 몇번이나 나고서야 드디어 정답이다,, 계속 50퍼 부근에서 '틀렸습니다' 나오길래 뭐가 문젠가 싶었는데 알고보니 맨 아래 초기화 코드에서 범위 설정을 잘못 해줬다. ^^

이 문제도 DFS, BFS 모두 사용가능하지만 나는 깊이우선탐색으로 구현했다. 일단 두 가지 단계가 필요한데, 먼저 이분그래프인지 를 알려면 모든 정점을 탐색하며 인접한 정점끼리는 다른 색으로 색칠을 해줘야 한다. RED 2, BLUE 3으로 색칠해줬다. 모두 색칠했으면, 색칠된 그래프를 탐색하며 인접한 정점의 색깔이 다른지 같은지 비교해봐야한다. 결과적으로 같다면 NO, 다르다면 YES를 출력하면 된다.

미로 문제처럼 2차원 좌표를 이용한 것이 아니므로, 그래프(G)는 행렬처럼 표현하고자 2차배열을 쓰되 1 -> 3 으로 가는 에지를 표현했었는데, 이 방법을 쓰니 메모리 초과 문제가 났다. 그래서 vector를 사용해 리스트 형태로 표현했다. (마치 나무-잎 그래프처럼?) 각 노드에 대해 다른 노드로 가는 에지가 있는 경우에만 그래프에 하나씩 추가해줬다. 그리고 노드 방문여부를 체크하는 isMarked는 이진값을 담지 않고 0, 1, 2, 3으로 RED, BLUE 색을 칠할 수 있게끔 했다. 실제로 그래프에 칠하지 않은 이유는 코드 짜는 게 번거로워질까봐 그랬는데.. 음 아무래도 isMarked에 일렬로 담는게 깔끔한 거 같다.

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

#define RED 2
#define BLUE 3

int T;
int v, e;
vector<int> G[20001];
int isMarked[20001] = { 0 };

void recursiveDFS(vector<int> G[20001], int start) {
	if (!isMarked[start]) {
		isMarked[start] = RED;
	}
	for (int i = 0; i < G[start].size(); i++) {
		int next = G[start][i];
		if (!isMarked[next]) {
			if (isMarked[start] == RED) {
				isMarked[next] = BLUE;
			}
			else if (isMarked[start] == BLUE) {
				isMarked[next] = RED;
			}
			recursiveDFS(G, next);
		}
	}
	return;
}

bool isBipartiteGraph() {
	for (int i = 0; i < v; i++) {  // i는 실제 정점
		for (int j = 0; j < G[i].size(); j++) { // j는 i와 에지로 연결된 또 다른 정점들의 인덱스
			int next = G[i][j]; // i(기준; 실제정점) -> next(i행 j열의 숫자; 다음정점)
			if (isMarked[i] == isMarked[next]) {
				//cout << "NO" << '\n';
				return false;
			}

		}
	}
	//cout << "YES" << '\n';
	return true;
}

int main(void) {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> v >> e;
		for (int j = 0; j < e; j++) {
			int x, y;
			cin >> x >> y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		
		for (int k = 0; k < v; k++) {
			if (!isMarked[k]) {
				recursiveDFS(G, k);
			}
		}
		if (isBipartiteGraph()) cout << "YES\n";
		else cout << "NO\n";

		// 초기화
		for (int i = 0; i < 20001; i++) {
			G[i].clear();
			isMarked[i] = 0;
		}
	}

	return 0;
}

 

열심히 풀긴 했지만 머리에 뭐가 남았는지 모르겠다.. 하다가 도저히 의문이 안 풀려서 다른 분들이 질문한 걸 참고했다. 메모리초과나 Segfault 런타임에러는 언제 마주쳐도 어렵다. BFS, DFS를 1차원 2차원에서 자유자재로 사용하도록 더 풀어봐야겟다