백준 C# - 1707 +) 풀이

이분 그래프

그래프의 모든 정점을 서로 다른 두가지 색으로 칠할 수 있는 그래프이다.

그래프의 정점을 두 그룹으로 나누었을때 같은 그룹에 속한 정점들 간에는 간선으로 연괼되어 있지 않고 서로 다른 그룹에 속한 정점들 간에만 간선으로 연결되어 있다.

출처 : https://mathworld.wolfram.com/BipartiteGraph.html

이분 그래프 알고리즘

주로 DFS나 BFS를 이용해서 구현한다.

01 그래프의 시작 정점을 색을 칠한다.

02 다음 정점은 현재 정점과 다른 색으로 칠한다.

03 만약 이미 색이 칠해져 있는데 현재 정점과 인접한 정점의 색이 같다면 이는 이분 그래프가 아니다.

---

문제를 풀어보자

DFS을 이용하자

static void DFS(int now, int group)
{
    visited[now] = group;

    foreach(int next in graph[now])
    {
        if (visited[next] == 0)
        {
            DFS(next, -group);
        }
        else if (visited[next] == visited[now])
        {
            isBipartite = false;
        }
    }
}

01 새로운 노드를 방문하는 경우

visited[next]가 0인 경우 아직 방문하지 않은 노드이다. 이 경우 해당 노드를 -group으로 마킹한다.

-group으로 하는 이유는 서로 다른 그룹을 나타내기 위해서이다. 예를 들어 현재 노드가 1이면 다음 노드는 -1로 마킹한다. 

if (visited[next] == 0)
{
    DFS(next, -group);
}

---

02 이미 방문한 노드를 다시 만나는 경우

visited[next]가 현재 노드 visited[now]와 같은 경우 이미 방문한 노드이다. 이 경우에는 현재 그래프가 이분 탐색 그래프가 아니라는 것을 의미한다.

else if (visited[next] == visited[now])
{
    isBipartite = false;
}

---

03 예시 문제1

1
4 3
1 2
2 3
1 4

---

04 예시 문제 2

1
4 4
1 2
2 3
3 4
4 2

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{

   class Program 
   {
        static List<int>[] graph;
        static int[] visited;
        static bool isBipartite;
        static void DFS(int now, int group)
        {
            visited[now] = group;

            foreach(int next in graph[now])
            {
                if (visited[next] == 0)
                {
                    DFS(next, -group);
                }
                else if (visited[next] == visited[now])
                {
                    isBipartite = false;
                }
            }
        }
        public static void Main()
        {
            int k = int.Parse(Console.ReadLine());
            while (k > 0)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int V = input[0];
                int E = input[1];

                graph = new List<int>[V + 5];
                visited = new int[V + 5];

                for(int i = 0; i<= V; i++)
                {
                    graph[i] = new List<int>();
                }

                for (int i = 0; i<E; i++)
                {
                    int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                    int u = edge[0];
                    int v = edge[1];

                    graph[u].Add(v);
                    graph[v].Add(u);
                }

                isBipartite = true;
                for (int i = 1; i <= V; i++)
                {
                    if (visited[i] == 0)
                    {
                        DFS(i,1);
                    }
                }
                if (isBipartite) Console.WriteLine("YES");
                else Console.WriteLine("NO");
                

                k--;
            }
            
        }
   }
}