백준 1707 Java: 이분 그래프를 BFS 2-Coloring으로 판별하기

백준 1707의 핵심은 graph의 모든 edge가 서로 다른 두 color를 잇도록 색칠할 수 있는지 확인하는 것이다. 처음 풀 때 이분 그래프의 정의가 선명하지 않아 약 일주일 동안 문제를 바라봤고, 결국 “인접한 두 vertex를 반대 색으로 칠한다”는 문제로 연결했다.

이분 그래프와 2-Coloring

vertex 집합을 두 group으로 나누고 같은 group의 vertex끼리는 edge가 없게 만들 수 있으면 bipartite graph다. 이를 color 1과 -1로 표현하면 모든 edge (u, v)에서 다음 조건을 만족해야 한다.

color[u] != color[v]

BFS로 한 vertex에 1을 주고 neighbor에는 -1, 그 neighbor의 neighbor에는 다시 1을 준다. 이미 칠한 neighbor가 현재 vertex와 같은 색이면 이분 그래프가 아니다.

연결되지 않은 Component도 모두 시작해야 한다

graph 전체가 connected라는 보장이 없다. vertex 1에서 BFS 한 번만 돌리면 다른 component의 odd cycle을 놓칠 수 있다.

1 -- 2       3 -- 4
              \  /
                5

첫 component가 이분 그래프여도 3-4-5-3 triangle 때문에 전체 graph는 이분 그래프가 아니다. 따라서 1..V를 순회하며 color가 0인 vertex마다 새 BFS를 시작한다. component마다 첫 color를 다시 1로 써도 된다. 서로 edge가 없으므로 group 이름은 독립적이다.

Java 풀이

original recursive DFS는 시작 vertex의 color를 먼저 지정하지 않았고, outer loop에서 group[i]처럼 test case index를 확인하는 bug가 있었다. 큰 graph에서는 recursion depth도 부담이 될 수 있어 iterative BFS로 고쳤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(
            new InputStreamReader(System.in)
        );
        int testCases = Integer.parseInt(reader.readLine());
        StringBuilder answer = new StringBuilder();

        while (testCases-- > 0) {
            StringTokenizer tokens = new StringTokenizer(reader.readLine());
            int vertices = Integer.parseInt(tokens.nextToken());
            int edges = Integer.parseInt(tokens.nextToken());

            List<Integer>[] graph = new ArrayList[vertices + 1];
            for (int vertex = 1; vertex <= vertices; vertex++) {
                graph[vertex] = new ArrayList<>();
            }

            for (int edge = 0; edge < edges; edge++) {
                tokens = new StringTokenizer(reader.readLine());
                int from = Integer.parseInt(tokens.nextToken());
                int to = Integer.parseInt(tokens.nextToken());
                graph[from].add(to);
                graph[to].add(from);
            }

            int[] color = new int[vertices + 1];
            boolean bipartite = true;

            for (int start = 1; start <= vertices && bipartite; start++) {
                if (color[start] != 0) {
                    continue;
                }
                bipartite = colorComponent(graph, color, start);
            }

            answer.append(bipartite ? "YES" : "NO").append('\n');
        }

        System.out.print(answer);
    }

    private static boolean colorComponent(
        List<Integer>[] graph,
        int[] color,
        int start
    ) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        color[start] = 1;
        queue.add(start);

        while (!queue.isEmpty()) {
            int current = queue.remove();

            for (int next : graph[current]) {
                if (color[next] == 0) {
                    color[next] = -color[current];
                    queue.add(next);
                } else if (color[next] == color[current]) {
                    return false;
                }
            }
        }
        return true;
    }
}

왜 이 판별이 맞나

BFS tree에서 시작점까지의 distance parity가 같은 vertex는 같은 color를 받고, parity가 다른 vertex는 반대 color를 받는다. 탐색 중 같은 color 사이의 edge를 발견했다면 그 edge와 BFS path가 odd cycle을 만든다. odd cycle이 있는 graph는 두 color로 칠할 수 없다.

반대로 모든 edge의 양 끝이 다른 color라면 color 1인 집합과 -1인 집합으로 graph를 나눌 수 있으므로 이분 그래프다.

확인할 경계 조건

• edge가 없는 isolated vertex: 어느 group에 넣어도 되므로 YES
• 여러 connected component: 모든 uncolored vertex에서 새 탐색
• self-loop: 같은 vertex가 자신의 neighbor이므로 즉시 NO
• duplicate edge: 판정에는 영향 없음
• even cycle: 2-coloring 가능
• odd cycle: 2-coloring 불가능

adjacency list에서 각 vertex와 edge를 상수 번 확인한다.

• 시간 복잡도: O(V + E)
• 공간 복잡도: O(V + E)

graph 표현과 traversal의 기초는 그래프와 DFS·BFS, DFS 순서 구현은 백준 24479·24480에서 이어서 볼 수 있다.

참고 자료

• 백준 1707 이분 그래프
• Java ArrayDeque API