이분 그래프 (백준 1707)

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

1707번: 이분 그래프

 

이분그래프

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.

---

풀이를 위한 아이디어 : 이분그래프의 하나의 간선에 연결된 두 노드의 색상은 서로 달라야 한다.

---

모든 노드에 대해 bfs를 수행하면서 연결된 노드와 서로 색상이 다른지 확인해야 한다.

 

변수

방문처리와 색상확인을 동시에 수행하는 int[] chk 배열을 뒀다.

• -1 : 아직 방문하지 않은 노드
• 0 : 빨간색
• 1 : 파란색

 

풀이순서

1. 모든 노드에 대해 반복문을 수행하며 방문하지 않았으면 bfs함수를 수행

static boolean solve(){

        for(int i=1;i<V+1;i++){
            if(chk[i]==-1){
                if(!bfs(i)) return false;
            }
        }
        return true;
    }

chk[i]가 -1인 경우(아직 방문하지 않은 노드)에 대해 bfs함수를 수행하는 것을 볼 수 있다.

 

2. bfs 시작점은 0(빨간색)으로 색칠했다. 1(파란색)으로 해도 됨. 인접한 노드에 대해선 다른 색상을 칠하기

static boolean bfs(int node){

        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{node,0});
        chk[node]=0;

        while(!q.isEmpty()){
            int[] c = q.pollFirst();
            int n = c[0];
            int color = c[1];

            for(int i : graph[n]){
                if(chk[i]==color){
                    return false;
                }
                if(chk[i]==-1){
                    chk[i] = (color + 1)%2;
                    q.offer(new int[]{i,chk[i]});
                }
            }
        }


        return true;
    }

서로 다른 색상을 칠하기 위해 모듈러 연산을 사용했다.

0(빨간색)이면 1(파란색)
1(파란색)이면 0(빨간색)

 

연결된 노드의 색상(chk[i])가 현재 색상(color)와 같으면 이분 그래프를 형성할 수 없으므로 false를 리턴했다.

 

 

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;


public class Main {

    static int T;
    static int V,E;
    static List<Integer>[] graph;
    static int[] chk;

    static boolean bfs(int node){

        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{node,0});
        chk[node]=0;

        while(!q.isEmpty()){
            int[] c = q.pollFirst();
            int n = c[0];
            int color = c[1];

            for(int i : graph[n]){
                if(chk[i]==color){
                    return false;
                }
                if(chk[i]==-1){
                    chk[i] = (color + 1)%2;
                    q.offer(new int[]{i,chk[i]});
                }
            }
        }


        return true;
    }
    static boolean solve(){

        for(int i=1;i<V+1;i++){
            if(chk[i]==-1){
                if(!bfs(i)) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

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

        for(int t=0;t<T;t++){
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            graph = new List[V+1];
            chk = new int[V+1];
            Arrays.fill(chk,-1);

            for(int i=1;i<V+1;i++){
                graph[i] = new ArrayList<>();
            }
            for(int i=0;i<E;i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph[a].add(b);
                graph[b].add(a);
            }

            if(solve()){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }



    }

}