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

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

 

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

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

---

1.  아이디어

 

BFS 알고리즘과 방문 체크를 응용해서 해결할 수 있다.

---

2. 문제풀이

 

이분 그래프의 조건이 정점을 두 집합으로 분할했을 때, 각 집합의 정점끼리는 서로 인접하지 않아야 한다.(그래프가 두 개로 쪼개지는거 아니다.) 두 집합에 대해 한 집합의 정점을 빨간색, 다른 집합의 정점을 검은색으로 칠한다고 생각하면 이분 그래프를 만족하려면 빨간색과 검정색이 퐁당퐁당 나오는 그래프가 되면 된다. 구현은 BFS를 활용해서 그래프를 탐색하며 번갈아 색깔을 칠해주고 같은 색이 인접하게 칠해지는 경우 이분 그래프가 아닌 것으로 판단했다. 색을 칠하는 것이 방문 체크가 되므로 방문안한 노드를 WHITE, 색이 칠해진 노드는 RED 또는 BLACK으로 생각하고 BFS에서 큐 전체를 비울때마다 색을 바꿔주는 방식으로 구현했다.

주어진 그래프가 하나의 그래프가 아닐 수 있음에 주의해야하고 단순한 사이클은 짝수 크기면 이분 그래프가 가능한 점에 주의해야 한다.

---

3. 코드

 

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

public class Main {

    private static final int WHITE = 0;
    private static int RED = -1;
    private static int BLACK = 1;

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

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

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i <= V; i++) {
                adj.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());

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

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

            for (int i = 1; i <= V; i++) {
                if (visited[i] == WHITE) {
                    boolean result = bfs(i, adj, visited);
                    if (!result) {
                        isBipartiteGraph = false;
                        break;
                    }
                }
            }

            if (isBipartiteGraph) sb.append("YES\n");
            else sb.append("NO\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static boolean bfs(int start, List<List<Integer>> adj, int[] visited) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);

        visited[start] = RED;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int node = q.poll();

                for (int next : adj.get(node)) {
                    if (visited[next] == RED) return false;

                    if (visited[next] == WHITE) {
                        q.offer(next);
                        visited[next] = BLACK;
                    }
                }
            }

            int tmp = RED;
            RED = BLACK;
            BLACK = tmp;
        }

        return true;
    }

}

---

4. 후기