[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크

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

🤔 문제

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

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

😮 문제 해결 방법

이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다.

따라서, 이분 그래프를 판별하는 방법은 다음과 같다.

1. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다.
2. BFS의 시작 정점을 임의의 색상으로 색칠한다. → colors[start] = RED(1);
3. 연결된 정점을 다른 색상으로 색칠한다. → colors[next] = colors[start] * -1;
4. 연결된 정점이 서로 동일한 색상을 가지는 경우 이분 그래프가 아니므로 false 반환한다.
5. 모든 정점이 각 독립된 그룹을 구성하면 이분 그래프이다.

방문 처리를 색상 배열로 체킹이 가능하다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_1707_이분_그래프 {

    private static List<List<Integer>> graph;
    private static int[] colors;
    private static final int RED = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        for(int testCase = 0; testCase < K; testCase++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();
            colors = new int[V+1];
            // 그래프 초기화
            for(int vertex =0 ; vertex <= V; vertex++) {
                graph.add(new ArrayList<>());
            }

            // 그래프 연결
            for(int edge = 0; edge < E; edge++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                graph.get(from).add(to);
                graph.get(to).add(from);
            }

            boolean rst = false;
            // 1. 색칠 되지 않은 모든 정점에 대해서
            for(int vertex = 1; vertex <= V; vertex++) {
                if(colors[vertex] == 0) {
                    rst = isBipartiteGraph(vertex, RED);
                }
                if(!rst) break;
            }
            if(rst) System.out.println("YES");
            else System.out.println("NO");
        }
        br.close();
    }

    private static boolean isBipartiteGraph(int start, int color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

                // 2. 시작 정점 임의의 색상으로 색칠
        colors[start] = color;

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int next : graph.get(cur)) {
                // 4. 인접 정점 색이 동일하면 이분 그래프가 아님
                if(colors[cur] == colors[next]) return false;

                // 3. 인접 정점 색칠 안된 경우 현재 정점 반대 색깔로 색칠
                                // 색상 배열을 통해 방문 여부 확인 가능
                if(colors[next] == 0) {
                    colors[next] = colors[cur] * -1;
                    queue.add(next);
                }
            }
        }
        return true;
    }
}