[C++]백준 - 1707번 문제

1707번: 이분 그래프 (acmicpc.net)

1707번: 이분 그래프

 

1707번 : 이분 그래프

---

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

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

입력

---

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

 

 

출력

---

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

 

 

---

 

생각해 볼 점

---

이분 그래프 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

이분 그래프를 만들려면, 노드를 두 그룹으로 나누어야 합니다.

 

Red 그룹과 Blue 그룹으로 나누었다고 생각하고,

 

같은 그룹 사이에 간선이 있으면 안되므로, BFS 혹은 DFS 탐색을 할 때, 다음과 같이 진행합니다.

 

1. 처음 탐색하는 노드를 Red 혹은 Blue로 지정

2. 간선이 이어진 노드를 반대 색상으로 지정함

3. 모든 노드를 탐색할 때까지 반복하되, 간선이 이어진 노드가 같은 그룹인 것을 발견했다면, NO를 출력 

 

 

코드

---

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

int main() 
{
	int K;
	cin >> K;
	for(int T = 0; T < K; T++)
	{
	    
       	int V, E;
	    cin >> V >> E;
	    
	    //동적 할당
       	vector<int> *graph = new vector<int>[V];
	    int *visited = new int[V];		//방문하지 않음 = 0, Red = 1, Blue = 2
	    fill_n(visited, V, 0);
	    queue<int> q;
	    
	    //입력부
	    for(int i = 0; i < E; i++)
	    {
	        int dep, des;
	        cin >> dep >> des;
	        graph[dep - 1].push_back(des - 1);
	        graph[des - 1].push_back(dep - 1);
	    }
	    
	    bool result = true;
	    for(int i = 0; i < V; i++)
	    {
	        if(visited[i] == 0)
	        {
        	    q.push(i);
        	    visited[0] = 1;
	        }
	    
    	    //DFS 순회 후 출력
    	    while(!q.empty())
    	    {
    	        int current = q.front();
    	        q.pop();
    	        for(int next : graph[current])
    	        {
                    if(visited[next] == 0) 
                    {
                        q.push(next);
                        visited[next] = (-1) * visited[current] + 3;	//반대 그룹으로 만듬
                    }
                    else if(visited[next] == visited[current])
                    {
                        result = false;
                        q = queue<int>();
                        break;
                    }
    	        }
    	    }
	    }
	    if(result) cout << "YES\n";
	    else cout << "NO\n";
	    
	    //동적할당 해제
	    delete[] graph;
	    delete[] visited;    
	}
	return 0;
}

 

그 외

---

저는 이 문제를 풀 때, 간선의 갯수가 홀수인 순환 형태의 도형이 발견되면 이분 그래프가 아니라 판단했습니다.

 

실제로 답은 맞았지만, 메모리초과가 난 김에 다른 사람의 풀이를 보니 더 정석적인 방법이 있어서 대체했습니다.

 

 

우측 아래처럼 꼭짓점 갯수가 짝수인 것은 포함되지 않습니다.

 

 

 

해당 풀이 :

#include <iostream>
using namespace std;

int V, E;
int **graph;
int *visited;

//스택 없는 DFS 순회
bool dfs(int current, int count)
{
    bool ret = true;
    count++;
    
    //처음 방문하는 노드의 경우, count 저장
    if(visited[current] == 0) visited[current] = count;
    
    //순회를 통해 순환 형태가 나타나면, 에지의 수가 홀수인지 확인하여 false를 반환
    else if((count - visited[current]) % 2 == 1) return false;
    
    
    for(int i = 0; i < V; i++)
    {
        if(graph[current][i] == 1) 
        {
            graph[current][i] = 2;
            graph[i][current] = 2;
            ret = (ret && dfs(i, count));
        }
    }
    return ret;
}


int main() 
{
	int K;
	cin >> K;
	for(int T = 0; T < K; T++)
	{
	    cin >> V >> E;
	    
	    //동적 할당
	    graph = new int*[V];
	    visited = new int[V];
	    fill_n(visited, V, 0);
	    for(int i = 0; i < V; i++)
	    {
	        graph[i] = new int[V];
	        fill_n(graph[i], V, 0);
	    }
	    
	    //입력부
	    for(int i = 0; i < E; i++)
	    {
	        int dep, des;
	        cin >> dep >> des;
	        graph[dep - 1][des - 1] = 1;
	        graph[des - 1][dep - 1] = 1;
	    }
	    
	    //DFS 순회 후 출력
	    if(dfs(0, 0)) cout << "YES\n";
	    else cout << "NO\n";
	    
	    //동적할당 해제
	    for(int i = 0; i < V; i++) delete[] graph[i];
	    delete[] graph;
	    delete[] visited;    
	}
	return 0;
}

 

 

 

그리고 이 문제는 간선 정보를 아래 예시1 처럼 정직하게 이차원 배열로 받으면 메모리 초과가 일어납니다. 필요한 에지의 정보만을 저장해야합니다.

 

예시 1)

011

100

100

 

예시 2)

Edge[0] = {1, 2}

Edge[1] = {0}

Edge[2] = {0]