[백준] 1707 - 이분 그래프

1. 문제

1707번: 이분 그래프

2. 개요

입력으로 주어진 그래프가 이분 그래프인지 아닌지를 판별하는 문제.

3. 풀이 및 코드

3-1. 풀이

인접 정점끼리 다른 색으로만 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프다.

따라서 DFS로 탐색하면서 첫 정점을 방문처리하며 1이라는 값을 넣어준다.

다음 인접 정점을 방문하지 않았다면 -1을 곱한 값을 넣어준다.

만약 방문한 정점인데 현 위치의 값과 똑같다면 이분 그래프가 아니므로 chk를 True로 바꿔 이분 그래프라는 처리를 해준다.

모든 정점에 대한 탐색이 완료되었다면 chk의 값에 따라 답을 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(300000)

T = int(sys.stdin.readline())

for t in range(T):
    chk = False

    V, E = map(int, sys.stdin.readline().split())

    visited = [0 for i in range(V+1)]
    graph = [[] for i in range(V+1)]

    for i in range(E):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    def DFS(n):
        global chk

        for nxt in graph[n]:
            if visited[nxt] != 0:
                if visited[nxt] == visited[n]:
                    chk = True
                    return

                else:
                    continue

            visited[nxt] = -visited[n]
            DFS(nxt)

    for i in range(V+1):
        if visited[i] == 0:
            visited[i] = 1
            DFS(i)

    if chk:
        print('NO')

    else:
        print('YES')

3-3. C#

namespace boj_1707
{
    internal class Program
    {
        static bool chk;
        static List<List<int>> graph;
        static int[] visited;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int T = int.Parse(sr.ReadLine());

            for (int t = 0; t < T; t++)
            {
                chk = false;

                string[] input = sr.ReadLine().Split();
                int V = int.Parse(input[0]);
                int E = int.Parse(input[1]);

                visited = new int[V + 1];
                graph = new List<List<int>>();

                for (int i = 0; i < V + 1; i++)
                    graph.Add(new List<int>());

                for (int i = 0; i < E; i++)
                {
                    string[] info = sr.ReadLine().Split();
                    int a = int.Parse(info[0]);
                    int b = int.Parse(info[1]);

                    graph[a].Add(b);
                    graph[b].Add(a);
                }
                
                for (int i = 0; i < V + 1; i++)
                {
                    if (visited[i] == 0)
                    {
                        visited[i] = 1;
                        DFS(i);
                    }
                }

                if (chk)
                    sw.WriteLine("NO");

                else
                    sw.WriteLine("YES");
            }
            sw.Close();
        }

        static void DFS(int n)
        {
            foreach (int nxt in graph[n])
            {
                if (visited[nxt] != 0)
                {
                    if (visited[nxt] == visited[n])
                    {
                        chk = true;
                        return;
                    }

                    else
                        continue;
                }

                visited[nxt] = -visited[n];
                DFS(nxt);
            }
        }
    }
}