[BOJ] 백준 1707. 이분 그래프

문제

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

---

풀이

 이분 그래프를 판별하는 문제이다. 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 말한다.

 

 풀이는 간단한데, 방문 시 1과 -1의 값으로 번갈아가며 방문 배열을 채워나가고, 만약 이전 방문 배열 값과 다음 방문 배열 값이 같으면 NO를 출력하면 끝이다.

 

 그런데 여기서 주의해야할 것은 이분 그래프의 정의인데, 연결되지 않은 정점도 독립적인 그룹으로 이분 그래프의 조건을 만족한다.

https://nahwasa.com/entry/%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84-bipartite-graph

 

그래서 탐색을 시작할 시작점은 방문되지 않은 점이 대상이 된다. (즉 모든 정점이 연결되어 있다고는 가정되어있지 않다! 이것땜에 43프로에서 틀렸다.)

 

다음은 소스 코드이다.

---

소스 코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class B1707_이분그래프 {
    static int T, V, E;
    static ArrayList<Integer>[] list;
    static Queue<Integer> queue;
    static int[] colors;
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        T = sc.nextInt();
        for(int tc=0; tc<T;tc++){
            initValues();
            process();
        }
    }

    static void process(){
        boolean isValid = true;
        for(int v = 1; v<=V; v++){
            if(colors[v] == 0) {
                isValid = checkBipartiteGraph(v);
            }
            if(!isValid) break;
        }
        System.out.println(isValid?"YES":"NO");
    }

    static boolean checkBipartiteGraph(int start){
        queue = new ArrayDeque<>();
        queue.add(start);
        colors[start] = 1;

        while(!queue.isEmpty()){
            int v = queue.poll();
            for(int v2:list[v]){
                if(colors[v2] == 0){
                    colors[v2] = colors[v]*-1;
                    queue.add(v2);
                }
                if(colors[v2]==colors[v]){
                    return false;
                }
            }
        }
        return true;
    }

    static void initValues(){
        V = sc.nextInt();
        E = sc.nextInt();

        colors = new int[V+1];
        list = new ArrayList[V+1];
        for(int i = 0; i<V+1;i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i<E;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            list[st].add(ed);
            list[ed].add(st);
        }
    }
}