[Gold IV] 이분 그래프 - 1707

문제 링크

성능 요약

메모리: 326684 KB, 시간: 2456 ms

분류

너비 우선 탐색, 이분 그래프, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 23일 18:25:03

문제 설명

<p>그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.</p>

<p>그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.</p>

입력

<p>입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. </p>

출력

<p>K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.</p>

풀이

java코드 복사
import java.util.*;

public class Main {
    
    static int K; // 테스트 케이스 수
    static int V; // 정점의 수
    static int E; // 간선의 수
    static String answer;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] set;

    public static void main(String[] args) {
        
        int p1, p2; // 두 정점; 간선
        Scanner scan = new Scanner(System.in);
        K = scan.nextInt();
        
        while (K-- > 0) {
            answer = "YES";
            V = scan.nextInt(); // 정점
            E = scan.nextInt(); // 간선
            graph = new ArrayList<>();
        
            for (int i = 0; i < V; i++) {
                graph.add(new ArrayList<>());
            }
            
            for (int i = 0; i < E; i++) {
                p1= scan.nextInt() - 1;
                p2= scan.nextInt() - 1;
                
                // 양방향 간선 추가
                graph.get(p1).add(p2);
                graph.get(p2).add(p1);
            }
            
            set= new int[V];
            
            for (int i= 0; i < V; i++) {
                if (set[i]= 0) {
                    if (!bfs(i)) break;
                }
            }
            System.out.println(answer);
        }
        
    }
    
    // bfs
    public static boolean bfs(int n) {
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(n);
        set[n] = 1;
        
        while (!queue.isEmpty()) {
            n = queue.poll();
            for (Integer i : graph.get(n)) {
                if (set[n] == set[i]) {
                    answer = "NO";
                    return false;
                }
                if (set[i] == 0) {
                    set[i] = set[n] * -1;
                    queue.add(i);
                }
            }
        }
        
        return true;
    }    
}