백준 1707 자바 - 이분 그래프 (BOJ 1707 JAVA)

문제 : boj1707

 

 

  '그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.' 무슨말이냐면, 정점을 두개의 그룹으로 나눴을 때, 해당 그룹끼리는 간선이 없도록 나눌 수 있으면 이분 그래프라는 얘기이다. 아래의 그림을 보면 바로 이해가 될 것이다. 1,2,3은 이분 그래프를 그려봤다. 4는 이분 그래프가 아닌 경우이다.

  즉, 어떻게든 2 종류의 정점으로 나눌 때 간선 연결된 것 끼리 같은 종류만 아니면 된다 (4번의 경우 노란 정점 둘이 간선이 연결되었으므로 이분 그래프가 아니다. 그리고 다른 방식으로 2종류로 나눠도 모두 마찬가지로 이분 그래프가 될 수 없다.). 또 중요한점은 3번과 같이 간선이 연결 안됬더라도 이분 그래프로 친다.

 

  그럼 이걸 확인만 할 수 있으면 되는데, 이분 그래프가 뭔지만 알면 생각보다 이분 그래프인지 확인하는건 간단하다. 서로 서로소인 집합에 대해 dfs 혹은 bfs를 진행하면서 처음엔 종류1, 다음은 종류2, 다음은 종류1, ... 이렇게 반복하면서 체크하면 된다. 그리고 이렇게 체크하는 도중에 인접해 있는데 동일한 종류를 만난다면 이분 그래프가 아닌것이다.

 

  주의점은 일반적으로 dfs나 bfs 진행하는 것 처럼 방문배열을 체크하면 이미 지나온 정점에 대해 동일한 종류인지 확인할 수 없을 것이다. 따라서 방문 배열은 없이 진행하나, 동일 정점을 두 번 갈 필요는 없다. 즉 인접한 정점에 대해서는 매번 체크하지만 이미 왔던(이미 체크했던) 정점으로 진행은 하면 안된다. 서로소인 집합을 찾는 방법은, 26~27 line 처럼 진행하면 된다. 모든 정점을 순서대로 확인하다가, 아직 체크되지 않은 지점을 발견하면 거기서부터 bfs, dfs를 진행하는걸 모든 정점을 확인할때까지 하는 것이다. 추가로 내 경우엔 시간을 줄이기 위해 chk 배열을 넣어서 위의 '3'과 같이 연결되지 않은 정점에 대해 체크 자체를 제외함으로써 시간을 줄였다(백트래킹. 글 작성 시점에서 자바코드 중엔 가장 빠름. 이 부분을 안넣으면 가장 빠르지 않다.). 코드에서 참고로 boolean은 알다시피 true, false인데, Boolean은 true, false외에 null도 가능하다. 내 경우엔 null이면 아직 체크하지 않은 것이고, true와 false로 종류를 둘로 나누었다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack;

public class Main extends FastInput {
    private void solution() throws Exception {
        int k = nextInt();
        StringBuilder sb = new StringBuilder();
        while (k-->0) {
            int v = nextInt();
            int e = nextInt();
            ArrayList<Integer>[] edges = new ArrayList[v+1];
            for (int i = 1; i <= v; i++) edges[i] = new ArrayList<>();
            boolean[] chk = new boolean[v+1];
            while(e-->0) {
                int a = nextInt();
                int b = nextInt();
                chk[a] = chk[b] = true;
                edges[a].add(b);
                edges[b].add(a);
            }
            Boolean[] arr = new Boolean[v+1];
            boolean answer = true;
            for (int i = 1; i <= v && answer; i++) {
                if (arr[i]!=null || !chk[i]) continue;
                Stack<Integer> stk = new Stack<>();
                stk.add(i);
                arr[i] = true;
                while(!stk.isEmpty() && answer) {
                    int cur = stk.pop();
                    for (int j = 0; j < edges[cur].size(); j++) {
                        int next = edges[cur].get(j);
                        if (arr[next] == null) {
                            arr[next] = !arr[cur];
                            stk.add(next);
                        } else if (arr[next] == arr[cur]) {
                            answer = false;
                            break;
                        }
                    }
                }
            }
            sb.append(answer?"YES\n":"NO\n");
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}