[BOJ/Graph] 백준 1707 - 이분 그래프 (Java)

1707 - 이분 그래프

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

문제

이분 그래프(Bipartite Graph)
: 그래프의 정점의 집합을 둘로 분할해 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할한 그래프

입력
첫째 줄: 테스트 케이스 개수 K
각 테스트 케이스 첫째 줄: 그래프 정점의 개수 V, 간선의 개수 E (각 정점에는 1부터 V까지 차례로 번호)
둘째 줄 ~ E개 줄: 인접한 두 정점의 번호 u, v (u != v, 간선의 대한 정보)
출력: 이분 그래프 O -> YES / X -> NO 순서대로 출력

---

풀이

이분 그래프

그래프의 모든 정점을 두 그룹(A, B)로 나눴을 때 인접한 두 정점이 같은 그룹 속하지 않게 나눌 수 있어야 함

 = 인접한 정점은 항상 반대편 그룹이어야 함

 

• 시작 노드 색(1) 칠함 / BFS로 탐색하며 연결된 노드 반대 색(-1) 칠함
• `color[next] == 0`: 아직 방문 X 노드 -> 반대 색으로 칠하고 큐에 추가
• `color[next] == color[cur]`: 이미 같은 색으로 칠해진 인접 정점 => 이분 그래프 X

static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    color[start] = 1;

    while (!queue.isEmpty()) {
        int cur = queue.poll();

        for (int next : graph.get(cur)) {
            if (color[next] == 0) {
                color[next] = -color[cur];
                queue.offer(next);
            } else if (color[next] == color[cur]) {
                flag = false;
                return;
            }
        }
    }
}

---

코드

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

// 이분 그래프
public class boj_1707 {
    static int[] color;
    static List<List<Integer>> graph;
    static boolean flag;

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int next : graph.get(cur)) {
                if (color[next] == 0) {
                    color[next] = -color[cur];
                    queue.offer(next);
                } else if (color[next] == color[cur]) {
                    flag = false;
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int K = Integer.parseInt(br.readLine());
        while (K-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

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

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                graph.get(u).add(v);
                graph.get(v).add(u);
            }

            color = new int[V + 1];
            flag = true;

            for (int i = 1; i <= V; i++) {
                if (color[i] == 0) bfs(i);
            }

            sb.append(flag ? "YES" : "NO").append("\n");
        }

        System.out.println(sb);
    }
}