이분그래프

백준 1707. 이분 그래프

 

처음 문제를 봤을땐 좀 이해하기 힘들었는데, 예제를 통해 그림을 그려보면 감이 좀 잡힌다.

 

예제분석

CASE 1.

1,2,3번 정점이 있고, (1,2)와 (2,3) 간선이 이어져있는 형태이다.

분석해보면, [1,2]와 [3]으로 집합을 분리했을때 각 집합에 속한 정점끼리는 서로 인접하지 않는다는 것을 알 수 있다.

즉, 이분그래프인것이다.

 

 

CASE 2.

 

1,3번 정점이 서로 연결되어있지는 않지만, 그둘을 하나의 집합으로 묶었다고 해서 이분그래프가 되진 못한다. 나머지 집합이 서로 인접하기 때문이다(간선을 갖기 때문)

 

 

이분그래프

그렇다면 위 내용을 바탕으로, 이분그래프를 정의해보자면 다음과 같다.

 

이런식으로 정점을 두 진영으로 나누었을때, 서로 다른 진영끼리는 연결될 수 있으나 같은 진영 안에선 연결 될 수 없는 형태인것이다.

 

이는 색깔로 구분했을때 더욱 구별하기 쉽다. 1번정점-3번정점-2번정점 순으로 연결되어있는데, 순서대로 주황-회색-주황 순으로 순회할 수 있다. 즉, 인접한 정점을 방문하려고 할때 주황-주황과 같이 같은 색깔이 나오면 안된다.

이를 정리하자면, 하나의 간선이 연결하는 두 정점은 서로 다른 색을 가져야만 한다. 그래야 이분그래프인 것이다!

이러한 '퐁당퐁당' 특성을 생각하면 풀이는 간단해진다. 그래프 자체를 순회하면서, 퐁당퐁당이 아닌 퐁퐁/당당이 나오는 부분을 찾으면 되는것이다. 즉, 주황이 연속 두번 나오거나 회색이 연속 두번 나오면 안된다.

 

 

이렇게 이 문제의 포인트는 역으로 생각하는것이었다. 정점의 조합을 찾아서 연결됐는지 찾고~ 이럴 필요가 없다. 그냥 이분그래프의 특성에 부합한지 찾는것이다. 그 특성이 바로 '간선이 연결하는 두 정점이 서로 다른 진영의 색깔을 가지고 있는지' 확인하는것이다.

 

 

풀이방법

이러한 '퐁당퐁당' 특성을 어떻게 확인 할 수 있을까?

위 예제를 다시 가져와보자.

(1) 1번을 시작점으로 하고, 주황색 속성을 부여한다.

(2) 1번과 연결된 3번 정점엔 회색 속성을 부여한다.

(3) 3번과 연결된 2번 정점엔 주황색 속성을 부여한다.

(3) 2번과 연결된 4번 정점엔 회색 속성을 부여한다.

(3) 4번과 연결된 5번 정점엔 주황색 속성을 부여한다.

(3) 5번과 연결된 6번 정점엔 회색 속성을 부여한다.

별다른 문제가 없었다. 실제로 그림에서도 명확히 이분그래프이다.

 

 

그렇다면 반례는 어떨까?

 

(1) 1번을 시작점으로 하고, 주황색 속성을 부여한다.

(2) 1번과 연결된 2번 정점엔 회색 속성을 부여한다.

(3) 2번과 연결된 4번 정점엔 주황색 속성을 부여한다.

     2번과 연결된 3번 정점엔 주황색 속성을 부여한다.

(4) 3번과 연결된 4번 정점엔 회색 속성을 부여한다.

 

=> 4번 정점에 대한 색깔 부여가 상충된다. 즉, 퐁당퐁당 특성을 만족하지 못해 이분탐색 그래프가 될 수 없는것이다.

 

 

위 과정을 코드로 구현하기 위해서 그래프 순회인 BFS나 DFS를 사용할 수 있다. 개인적으론 BFS가 편해서 이를 통해 구현했다. 그래프를 순회하면서, 이전에 방문한적이 있으며, 할당하려는 색과 다른 색을 할당하려고 할 경우 이분탐색 그래프의 특성을 만족하지 못해 "NO"를 출력하는것이 포인트이다.

 

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

/** 이분 그래프
 * 그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할 할 수 있을때
 * 그러한 그래프를 특별히 이분그래프라 부른다.
 * 그래프가 입력으로 주어졌을때 이분그래프인지 판별하는 프로그램을 작성하라.
 *
 * 입력
 * 테스트케이스 2<=K<=5
 * 각 테케의 1<=정점갯수V<=2만과 1<=간선갯수E<=20만
 * 각 정점은 1~V까지 번호가 붙어있음.
 * E개 줄에 걸쳐 간선에 대한 정보(u,v)가 주어짐.
 *
 * 출력
 * 이분그래프이면 YES, 아니면 NO를 출력한다.
 *
 * 풀이
 * 이분그래프 특성을 이용한다. dfs/bfs로 그래프를 순회하며 모든 정점 방문해보면서 할당된 색이 바뀌는 일이 있는지 확인함
 * 연결요소가 여러개일 수 있으므로 상태가 0인게 있으면 계속 순회 시도
 * 0=할당전 1=주황색 2=회색
 */
public class Boj_1707 {
    static StringBuilder sb = new StringBuilder();
    static List<ArrayList<Integer>> graph;
    static int[] colors;
    static boolean stopFlag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int t=0; t<K; t++) {
            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+1; i++) graph.add(new ArrayList<>());
            for(int i=0; i<E; i++) {
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());
                graph.get(v1).add(v2);
                graph.get(v2).add(v1);
            }
            colors = new int[V+1];
            stopFlag = false;
            for(int i=1; i<V+1; i++) {
                if(colors[i] == 0) bfs(i);
                if(stopFlag) break;
            }

            if(stopFlag) sb.append("NO").append('\n');
            else sb.append("YES").append('\n');
        }
        System.out.println(sb);
    }

    public static void bfs(int startV) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(startV);
        colors[startV] = 1;
        while(!q.isEmpty()) {
            int curr = q.poll();
            int nextColor = (colors[curr]==1 ? 2:1);
            for(int next : graph.get(curr)) {
                //이전에 방문한적 없음(0)이면 새로운 색깔 할당,
                // 이전에 방문한적 있음(!=0)이면 현재색과 같은지 확인후 다르면 이분그래프가 아니므로 종료해야함.
                if(colors[next] == 0) {
                    colors[next] = nextColor;
                    q.add(next);
                }
                else {
                    if(colors[next] == nextColor) continue;
                    else {
                        stopFlag = true;
                        return;
                    }
                }
            }
        }

    }
}