[백준] 1707: 이분 그래프 (Java, Python)

이분 그래프

백준 그래프 BFS 2-Coloring Python Java

문제 분석

• 그래프의 정점을 두 집합으로 분할하여, 같은 집합 내 정점끼리 인접하지 않도록 할 수 있는지 판별
• 가능하면 이분 그래프(Bipartite Graph) → YES, 아니면 NO
• 제약: K ≤ 5 / V ≤ 20,000 / E ≤ 200,000
• 주의: 그래프가 비연결(disconnected)일 수 있음 → 모든 컴포넌트를 검사해야 함

접근법

• 핵심 아이디어: 이분 그래프 ⇔ 홀수 길이 사이클이 없음 ⇔ 2-coloring이 가능
• BFS 2-coloring: 각 정점에 0 또는 1 색을 칠하면서, 인접 정점이 같은 색이면 이분 그래프가 아님
• 비연결 그래프이므로 모든 미방문 정점에서 BFS를 시작

Tip: 색 전환은 color[v] = color[u] ^ 1 (XOR)로 간결하게 처리

풀이 (Python)

import sys
from collections import deque
input = sys.stdin.readline

K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    adj = [[] for _ in range(V + 1)]
    for _ in range(E):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    color = [-1] * (V + 1)
    ok = True

    for s in range(1, V + 1):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    ok = False
                    break
            if not ok:
                break
        if not ok:
            break

    print("YES" if ok else "NO")

풀이 (Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (K-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i <= V; i++) adj.add(new ArrayList<>());
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
            int[] c = new int[V + 1];
            Arrays.fill(c, -1);
            boolean ok = true;
            for (int s = 1; s <= V && ok; s++) {
                if (c[s] != -1) continue;
                c[s] = 0;
                Deque<Integer> q = new ArrayDeque<>();
                q.add(s);
                while (!q.isEmpty() && ok) {
                    int u = q.poll();
                    for (int v : adj.get(u)) {
                        if (c[v] == -1) {
                            c[v] = c[u] ^ 1;
                            q.add(v);
                        } else if (c[v] == c[u]) {
                            ok = false;
                            break;
                        }
                    }
                }
            }
            sb.append(ok ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
}

예제 트레이스

테스트 1: V=3, E=2, 간선: (1,3), (2,3)

BFS from 1:
  color[1] = 0
  1 → 3: color[3] = 1
  3 → 2: color[2] = 0  (1과 같은 색이지만 인접하지 않으므로 OK)

  충돌 없음 → YES ✓

---

테스트 2: V=4, E=4, 간선: (1,2),(2,3),(3,4),(4,2)

BFS from 1:
  color[1] = 0
  1 → 2: color[2] = 1
  2 → 3: color[3] = 0
  3 → 4: color[4] = 1
  4 → 2: color[4]=1 == color[2]=1 → 충돌!

  홀수 사이클 (2-3-4) 존재 → NO ✓

시간 복잡도

O(V + E)

공간 복잡도

O(V + E)

알고리즘 풀이 블로그