백준 1707번 이분 그래프

문제 링크입니다: https://www.acmicpc.net/problem/1707

문제에서 이분 그래프(Bipartite Graph)를 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프라고 정의합니다.

이분 그래프의 예시는 http://mathworld.wolfram.com/BipartiteGraph.html에서 확인할 수 있습니다.

이는 즉, DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 적용하여 서로 이어지는 노드끼리 같은 색깔이면  안 된다는 뜻입니다.(링크에서는 빨간색과 검은색으로 표시했습니다.)

정점의 집합을 둘로 분할하기 때문에 색깔은 2가지이면 되고 아직 방문하지 않은 노드를 0으로 표시하기 때문에 nodeColor[i]에는 0, 1, 2만 저장될 수 있습니다.

따라서, DFS 알고리즘을 적용하여 next를 방문하면서 nodeNum과 다른 색깔을 입히고 다시 그래프 정점들을 순회하면서 이분 그래프 여부를 판별하면 풀 수 있는 문제였습니다!

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

 

const int MAX = 20000 + 1;

 

int K, V, E;

vector<int> graph[MAX];

int nodeColor[MAX];

 

//color: 0 아직 방문 X, 1, 2는 각각 색깔

void DFS(int nodeNum, int color)

{

        nodeColor[nodeNum] = color;

 

        for (int i = 0; i < graph[nodeNum].size(); i++)

        {

                 int next = graph[nodeNum][i];

                 if (!nodeColor[next])

                         DFS(next, 3 - color);

        }

}

 

//서로 연결된 노드끼리 같은 색깔이면 이분 그래프 X

bool isBipartiteGraph(void)

{

        for (int i = 1; i <= V; i++)

                 for (int j = 0; j < graph[i].size(); j++)

                 {

                         int next = graph[i][j];

                         if (nodeColor[i] == nodeColor[next])

                                 return false;

                 }

        return true;

}

 

int main(void)

{

        cin >> K;

       

        for (int i = 0; i < K; i++)

        {

                 for (int j = 1; j < MAX; j++)

                         graph[j].clear();

                 memset(nodeColor, 0, sizeof(nodeColor));

 

                 cin >> V >> E;

 

                 for (int j = 0; j < E; j++)

                 {

                         int node1, node2;

                         cin >> node1 >> node2;

 

                         graph[node1].push_back(node2);

                         graph[node2].push_back(node1);

                 }

 

                 for (int j = 1; j <= V; j++)

                         if (nodeColor[j] == 0)

                                 DFS(j, 1); //1번 색깔부터 시작

 

                 if (isBipartiteGraph())

                         cout << "YES" << endl;

                 else

                         cout << "NO" << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~