[백준] 1707: 이분 그래프 - Java (그래프 알고리즘)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

  이분 그래프란? 

정점들은 두 개의 그룹 중(빨강과 파랑) 하나에 속하고, 빨간색 정점은 빨간색 정점과 연결될 수 없고, 파란색 정점은 파란색 정점과 연결될 수 없다. 즉 같은 색이 연결이 된다면 그 그래프는 이분 그래프가 아니다. 간단히 말해서, 연결은 항상 다른 색의 정점으로만 이루어진다. 

 

 

 

그래프를 두 그룹으로 정리해 본다면 아래 그림과 같이 정리가 되는 것을 볼 수 있다. 

절대 같은 색상끼리 연결이 안 되는 모습을 보여준다.

 

 

 

  이분 그래프?

1. DFS 혹은 BFS 로 확인할 수 있다.

2. 그래프의 모든 정점과 간선을 한 번만 탐색하므로, 시간 복잡도는 O(V + E) 이다.

 

 

  BFS 풀이

1. Queue에서 뺀 정점의 인근 정점을 확인한다.

2. 방문하지 않았다면 뺀 정점의 반대색을 부여한다.

3. 이미 방문을 했다면, 서로 같은 색인지 확인한다.

4. 서로 같은 색이라면 이분 그래프가 아니므로 중단한다.

 

*주의*

정점이 5개 있을 때, 모든 정점이 분리되어 있다고 해도 이분 그래프라 할 수 있으므로, 기본적으로 이분 그래프를 판별하는 변수는 true 로 설정해 놓는 것이 좋다.

 

 

 

  풀이

 

 

package src.Graph;

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

public class 이분그래프_1707 {

    // 1차: 해당 정점, 2차: 연결된 정점
    static List<Integer>[] graph;

    /**
     * 0: 방문 안 함
     * -1: 빨강
     * 1 : 파랑
     */
    static int[] color;

    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 List[V + 1];
            color = new int[V + 1];

            for(int i = 0; i <= V; i++){
                graph[i] = new ArrayList<>();
                color[i] = 0;
            }

            for(int i = 0; i < E; i++){
                StringTokenizer edges = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(edges.nextToken());
                int b = Integer.parseInt(edges.nextToken());

                graph[a].add(b);
                graph[b].add(a);
            }

            // main Solution
            int result = 1;
            for(int i = 1; i <= V; i++){
                int ans = 0;
                if(color[i] == 0){
                    result = isBipartite(i);
                    if(result == -1){
                        break;
                    }
                }
            }

            if(result == 1){
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }



        // while 문 끝
        }

        System.out.println(sb);


    }


    // s: 시작 정점, 반환: -1: false, 1: true
    static int isBipartite(int s){

        // 1: true, 2: false
        int check = 1;

        Queue<Integer> queue = new LinkedList<>();

        queue.add(s);

        color[s] = 1;

        while(!queue.isEmpty()){

            int pop = queue.poll();

            for(int i = 0; i < graph[pop].size(); i++){
                if(color[graph[pop].get(i)] == 0){
                    color[graph[pop].get(i)] = color[pop] == 1 ? -1 : 1;
                    queue.add(graph[pop].get(i));
                } else if(color[pop] + color[graph[pop].get(i)] != 0){
                    check = -1;
                    break;
                }
            }

            if(check == -1){
                break;
            }
        }

        return check;
    }


}