문제 접근

처음에는, 이분 그래프 탐색 알고리즘을 몰라서 문제를 읽고 이분 그래프가 되기 위한 조건은 사이클이 없으면 된다고 생각했다.
물론 사이클이 없는 그래프인 트리가 이분 그래프를 만족하는 것은 사실(트리의 레벨끼리 서로 다른 그룹에 넣으면 됨)이나, 트리가 아니여도 이분 그래프가 될 수 있다.
그 반례는 정점 네 개의 정사각형 모양의 사이클을 떠올리면 된다.
이 경우, 대각선 정점끼리 같은 그룹에 넣으면 이분 그래프가 될 수 있다.

이 문제를 풀면서 나름 의미있는 것들을 복습하고 또 새롭게 알게 되어서 정리하고자 한다.

순환 탐색

우선, 순환탐색을 처음에 떠올렸는데, 내가 아는 방법은 벨만포드나 플로이드워샬 밖에 없었다.
하지만, 문제에서 정점은 2만개, 간선은 20만개로 벨만포드는 V*E 이므로 40억, 플로이드워샬은 V^3 이므로 8~ 너무 크다...
결국엔 새로운 순환 탐색 방법이 필요했고, 찾아본 결과 dfs나 bfs로 쉽게 해결이 가능했다.
원리는 간단하다.

dfs와 bfs에서 다음 탐색을 넘기기 위해 이웃 노드들을 조사할 때, 자신의 부모가 아닌데 이미 방문한 노드가 있다면 순환이 존재하는 것이다.

물론, 이 풀이는 이 문제에서 틀렸지만 알면 유용할 것이라 생각한다.

이분 그래프 탐색 알고리즘

이분 그래프 탐색 알고리즘은 그래프 이론에서 꽤나 유명한 이론 같았다.
원리는 다음과 같다. 색상을 두 개로 구분한다.
그리고, dfs나 bfs를 진행하고, 이웃한 노드 중에 자신과 동일한 색이 칠해진 녀석이 있다면 사이클이 존재하는 것임.
그리고, 자신의 이웃 노드는 자신과 다른 색으로 칠해나가면 된다.

문제 풀이

dfs 풀이

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

class Main {
    static boolean hasCycle = false;
    static int[] nodeColor;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();
            nodeColor = new int[V + 1];
            hasCycle = false;
            for (int i = 0; i <= V; 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);
            }

            Arrays.fill(nodeColor, 0);

            for (int v = 1; v <= V; v++) {
                if (nodeColor[v] == 0) {
                    dfs(v, 1);
                }
                if (hasCycle) {
                    sb.append("NO\n");
                    break;
                }
            }

            if (!hasCycle) sb.append("YES\n");
        }

        System.out.print(sb);
    }

    private static void dfs(int curNode, int curColor) {
        nodeColor[curNode] = curColor;
        if (hasCycle) return;
        int inColor = (curColor == 1) ? 2 : 1;
        for (int inNode : graph.get(curNode)) {
            if (nodeColor[inNode] == curColor) {
                hasCycle = true;
                return;
            } else if (nodeColor[inNode] == 0) {
                dfs(inNode, inColor);
            }
        }
    }
}

bfs 풀이

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

class Main {
    static boolean hasCycle = false;
    static int[] nodeColor;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();
            nodeColor = new int[V + 1];
            hasCycle = false;
            for (int i = 0; i <= V; 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);
            }

            Arrays.fill(nodeColor, 0);
            LinkedList<Node> q = new LinkedList<>();
            for (int v = 1; v <= V; v++) {
                if (nodeColor[v] == 0) {
                    q.add(new Node(v, 1));
                    nodeColor[v] = 1;
                    while (!q.isEmpty()) {
                        Node curNode = q.poll();
                        int inColor = (curNode.color == 1) ? 2 : 1;
                        for (int inV : graph.get(curNode.v)) {
                            if (nodeColor[inV] == curNode.color) {
                                hasCycle = true;
                                sb.append("NO\n");
                                break;
                            } else if (nodeColor[inV] == 0) {
                                nodeColor[inV] = inColor;
                                q.add(new Node(inV, inColor));
                            }
                        }
                        if (hasCycle) break;
                    }
                }
                if (hasCycle) break;
            }

            if (!hasCycle) sb.append("YES\n");
        }

        System.out.print(sb);
    }
}

class Node {
    int v;
    int color;

    Node(int vNumber, int color) {
        this.v = vNumber;
        this.color = color;
    }
}