[1707] - 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

이분 그래프

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

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

- 쉽게 말하면 인접한 정점이 다른색이어야 된다.

 

접근 방식

색을 1과 -1로 설정해 그래프를 돌며 탐색을 안했으면 이전 색 x-1을 해주기. 시작 정점을 1부터 탐색 하였더니 틀렸다.

질문검색에서 반례를 찾아보니 연결이 안되있는 정점이 있을 수도 있어, 모든 정점에 대해 검사하는 반복문을 하나 더 씌워줬다.

 

문제 풀이

• 그래프 생성
• 정점을 순회하면서 탐색하지 않았다면(check값이 0 이면) 그 정점을 1로 설정, 큐에 넣고 bfs 탐색
• 만약 현재와 다음 탐색할 정점의 색이 같다면 이분 그래프가 아니니 false로 변경후 탈출.
• 출력

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _1707
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int test = int.Parse(Console.ReadLine());

            for(int t = 0; t<test; t++)
            {
                //ve[0] = 정점, ve[1] = 간선 개수
                int[] ve = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                //그래프
                Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
                for (int i = 1; i <= ve[0]; i++)
                    graph[i] = new List<int>();
                for(int i = 0; i < ve[1]; i++)
                {
                    int[] line = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                    graph[line[0]].Add(line[1]);
                    graph[line[1]].Add(line[0]);
                }

                Queue<int> que = new Queue<int>();
                int[] check = new int[ve[0] + 1];
                bool is_graph = true;

                //그래프 연결이 안됬을 수도 있으니 전부 탐색
                foreach(int key in graph.Keys)
                {
                    if(check[key] == 0)
                    {
                        que.Enqueue(key);
                        check[key] = 1;

                        while (que.Count > 0)
                        {
                            int point = que.Dequeue();

                            foreach (int p in graph[point])
                            {
                                if (check[p] == 0)
                                {
                                    check[p] = check[point] * (-1);
                                    que.Enqueue(p);
                                }
                                else if (check[p] == check[point])
                                {
                                    is_graph = false;
                                    break;
                                }
                            }
                        }

                    }
                }
                if (is_graph)
                    stb.AppendLine("YES");
                else
                    stb.AppendLine("NO");
            }

            Console.WriteLine(stb);
        }
    }
}