[BOJ 1707] 이분 그래프 (Java, BFS)

---

문제 링크

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

1707번: 이분 그래프

---

풀이

- BFS 로 각 노드에 대한 색상 (0, 1)을 번갈아 가며 지정

- 이때 연결된 노드의 색상이 동일한 경우 이분 그래프가 아님 

- 테스트 케이스별로 BFS 탐색시 시간 복잡도 O(V + E) 만큼 시간 소요

 

실수

- 양방향 그래프 설정을 하지 않고 탐색을 해서 틀림

 

 

이분그래프 개념 참고 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int K, V, E;

    static List<Integer>[] adj;

    static int[] COLOR;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken()); // 테스트 케이스
        COLOR = new int[20001];
        while(K > 0) {
            K -= 1;

            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken()); // 정점
            E = Integer.parseInt(st.nextToken()); // 간선

            adj = new ArrayList[V + 1];
            for(int i = 1; i <= V; i++) adj[i] = new ArrayList<>();

            for(int i = 1; i <= E; i++) { // 양방향 그래프 처리하지 않을 경우 틀림
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                adj[from].add(to);
                adj[to].add(from);
            }

            for(int i = 1; i <= V; i++) Collections.sort(adj[i]);

            pro();
        }

        br.close();
    }

    static boolean bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        COLOR[start] = 0;

        boolean result = true;
        while(!que.isEmpty()) {
            int x = que.poll();
            if(!checkBipartite(x)) {
                result = false;
                break;
            }

            for(int y : adj[x]) {
                if(COLOR[y] == -1) {
                    COLOR[y] = (COLOR[x] + 1) % 2; // 1인 경우 : blue, 0인 경우 red;
                    que.add(y);
                }
            }
        }

        return result;
    }

    static boolean checkBipartite(int node) {
        for(int n : adj[node]) {
            if(COLOR[n] == COLOR[node]) return false;
        }

        return true;
    }

    static void pro() {
        Arrays.fill(COLOR, -1);
    
        boolean isBipartite = true;
        for(int i = 1; i <= V; i++) {
            if(COLOR[i] == -1 && !bfs(i)) {
                isBipartite = false;
                break;
            }
        }

        String result = isBipartite ? "YES" : "NO";
        sb.append(result).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}