이번 문제는 백준 골드 4 이분 그래프 문제이다.
제목을 보고 그래프 문제이길래 흥미로워 보여 풀기로 마음 먹었다.
문제를 한 번 차근차근 읽어보도록 하자.
최대 2만개의 정점과, 20만개의 간선이 주어질 수 있다.
위 제약 조건 아래에서 그래프가 주어졌을 때, 이분 가능한지 판단하라.
일단 이 문제를 풀려면 이분 그래프가 무엇인지 알아야 한다.
이분 그래프(Bipartite graph)
이분 그래프는 이름 그대로, 두 집합으로 분할이 가능한 집합이다.
조금 더 자세하게 정의하면 각 정점들을 두 개의 집합으로 나누었을 때,
같은 집합에 포함된 정점들 간에는 간선이 없어야 한다.
아래와 같은 그래프가 이분 그래프이며, 색깔로 집합을 구분한다.
자 이제 이분 그래프가 무엇인지 알았으니, 어떻게 판별할지 고민해보자.
가장 큰 특징인 같은 집합의 노드끼리는 연결되지 않았음을 어떻게 확인할까?
집합에 정점을 집어넣는 모든 경우의 수를 다 탐색해보아야 할까?
완전탐색은 정점이 2만개이기 떄문에 시간이 말도 안되게 걸릴 것이다.
DFS + 색깔
위의 그래프에서 색깔을 이용해서 각 집합을 구분했었다.
DFS를 돌려서 색깔로 두 집합으로 구분이 가능한지 살펴 볼 수 있을까?
색깔로 취급할 int[] 배열을 하나 만들어서 색을 체크하도록 하고,
DFS를 우선 한 번 돌려서 두 집합으로 구분을 한 다음 더 작은 집합을 찾는다.
정점의 수가 더 작은 집합의 정점들로 부터 각각 DFS를 돌렸을 때,
색깔 배열의 상태가 변하지 않는다면 이분 그래프일 것이다.
이 논리를 코드로 구현했을 때, 시간초과가 발생하지 않을까?
곰곰히 생각해보니, 시간 초과가 문제가 아니라는 생각이 들었다.
애초에 이 논리는 끊어진 정점이 있다는 가정하에 이루어지며,
모두 이어진 그래프의 경우에는 판별이 불가능하다.
진짜 DFS + 색깔
사실 아이디어는 맞았는데, 논리가 잘못되었었다.
훨씬 간단하게 이분 그래프를 분별할 수 있는 방법이 인터넷에 있었다.
그것은 바로 DFS를 탐색하며 이어진 정점은 계속 반대 색깔로 갱신하는 것이다.
아래와 같이 코드로 구현하였다.
void dfs(int curr_node) {
if (!visit[curr_node])
visit[curr_node] = 1;
// 특정 색으로 변경
for (int i = 0; i < graph[curr_node].size(); i++) {
if (!visit[graph[curr_node][i]]) {
if (visit[curr_node] == 1)
visit[graph[curr_node][i]] = 2;
else if (visit[curr_node] == 2)
visit[graph[curr_node][i]] = 1;
dfs(graph[curr_node][i]);
}
}
}정점을 계속 반대 색으로 갱신한 뒤, 핵심은 이를 검사할 때에 있다.
만약 모든 연결된 정점을 검사할 때 연결된 정점에서 같은 색이 발견된다면?
그럼 이 그래프는 이분 그래프가 될 수 없다는 의미가 된다!
왜냐하면, 어떤 두 정점이 있다면 그 둘은 반드시 다른 색을 가져야 하기 때문이다.
그게 바로 이분 그래프의 정의 이기 때문이다.
bool check_bipartited() {
for (int i = 1; i <= vertex; i++) {
for (int j = 0; j < graph[i].size(); j++)
if (visit[i] == visit[graph[i][j]])
return false;
}
return true;
}
for (int j = 1; j <= vertex; j++)
if (!visit[j])
dfs(j);
if (check_bipartited())
cout << "YES" << '\n';
else
cout << "NO" << '\n';
clear_array();위와 같은 코드로 구현할 수 있다.
여러개의 테스트 케이스가 존재하기 때문에, 마지막엔 배열을 초기화 해준다.
혼자 생각해내기에는 아직 무리가 있는 문제였다.
이분 그래프를 판별 해낼 수 있는 아이디어를 생각하기가 매우 어려웠다.
이럴 때 일수록 더욱 개념을 잘 생각해야 하는 게 수학 문제를 푸는 것 같다.