[BOJ][Java] 1707번 이분 그래프

문제 설명

 

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

 

위의 문제는 그래프를 2개의 집합으로 나누었을 때 각각의 집합에 인접한 정점이 없는지를 확인하는 문제이다.

단순히 생각해 보면 한 정점의 바로 옆에 있는 정점을 다른 집합으로 정했을 때 문제가 없을지 확인하면 된다.

경우의 수를 생각해 보면 아래와 같은 경우가 있다.

 

첫 번째로 만약 일직선의 경우 1번 노드를 0 집합에 넣고

2번 노드를 1 집합 3번 노드를 0 집합에 넣는다면 해당 그래프는 

이분 그래프라고 할 수 있다. 따라서 일직선의 경우에는 이분 그래프의 조건을 만족한다.

 

두 번째로 순환그래프 중 문제가 발생하는 경우이다.

홀수개로 이루어진 정점이 순환되는 위와 같은 형태의 그래프에서는

1번과 3번 노드가 둘 다 0 집합에 들어가며 이분그래프의 조건을 만족하지 못한다.

 

마지막으로 순환그래프이면서 조건을 만족하는 경우이다.

짝수개로 이루어진 정점들이 순환하는 형태를 이루고 있다면

위와 같이 이분그래프의 조건을 만족한다.

 

이런 경우의 수들을 보면 결국 하나의 정점을 골라 DFS 탐색으로 끝까지 타고 들어가다

만약 인접한 노드가 동일한 집합에 속한다면 탐색을 멈추고 이분그래프가 아니라고 출력해 주면 된다.

 

package boj;

import java.util.*;
import java.io.*;


public class BOJ1707 {
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int[] check;
    static boolean even;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int K = Integer.parseInt(br.readLine());

        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();

            for(int j = 0; j <= V; j++){
                graph.add(new ArrayList<>());
            }

            visited = new boolean[V+1];
            even = true;
            check = new int[V+1];

            for(int j = 0; j < E; j++){
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());

                graph.get(s).add(e);
                graph.get(e).add(s);
            }

            for(int j = 1; j <= V; j++){
                if(even){
                    dfs(j);
                }else{
                    break;
                }
            }

            if(even){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }

        }
    }

    static void dfs(int start){
        visited[start] = true;

        for(int i: graph.get(start)){
            if(!visited[i]){
                check[i] = ((check[start] + 1) % 2);
                dfs(i);
            }else if(check[start] == check[i]){
                even = false;
            }
        }
    }
}