b.1707 이분 그래프

 

https://www.acmicpc.net/problem/1707

 

 

 

📌 자바(Java)로 푸는 이분 그래프 판별 문제 - 백준 1707 🚀

 

🔎 문제 개요

 

백준 1707번 - 이분 그래프 판별 문제입니다.

주어진 무방향 그래프가 이분 그래프인지 판별하는 것이 목표입니다.

 

이분 그래프란?

• 모든 정점을 두 개의 그룹으로 나눌 수 있는 그래프

• 같은 그룹 내 정점끼리는 서로 연결되지 않아야 함

• 즉, 인접한 정점은 항상 다른 그룹에 속해야 함

 

💡 예제 입력

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 1

💡 예제 출력

YES
NO

➡ 첫 번째 그래프는 이분 그래프이며, 두 번째 그래프는 이분 그래프가 아님

 

🛠 알고리즘 접근 방식

 

BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 활용한 그래프 색칠 알고리즘을 사용합니다.

 

✏️ 주요 고려 사항

 

✔ BFS를 사용하여 정점을 두 가지 색으로 칠하면서 탐색

✔ 인접한 정점이 같은 색이 된다면 이분 그래프가 아님

✔ 모든 정점이 연결되어 있지 않을 수 있으므로, 모든 정점에 대해 BFS 실행

✔ 이분 그래프면 YES, 아니면 NO 출력

 

🔹 Java 코드 해설

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

public class Main {

    static class Node {
        int num;
        boolean color;

        public Node(int num, boolean color) {
            this.num = num;
            this.color = color;
        }
    }

    static int T; // 테스트 케이스 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = stringToInteger(br.readLine());

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = stringToInteger(st.nextToken());  // 정점 개수
            int E = stringToInteger(st.nextToken());  // 간선 개수
            sb.append(logic(N, E, br));
        }
        System.out.println(sb);
    }

    // 그래프 판별 로직
    static String logic(int N, int E, BufferedReader br) throws IOException {
        ArrayList<Integer>[] list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            StringTokenizer stLogic = new StringTokenizer(br.readLine());
            int a = stringToInteger(stLogic.nextToken());
            int b = stringToInteger(stLogic.nextToken());

            list[a].add(b);
            list[b].add(a);
        }

        int[] colors = new int[N + 1]; // 0: 미방문, 1: 빨강, -1: 파랑

        for (int i = 1; i <= N; i++) {
            if (colors[i] == 0) { // 아직 방문하지 않은 정점
                if (!BFS(i, list, colors)) return "NO\n";
            }
        }

        return "YES\n";
    }

    // BFS를 활용한 이분 그래프 판별
    static boolean BFS(int start, ArrayList<Integer>[] list, int[] colors) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(start, true));
        colors[start] = 1; // 시작 정점은 1 (빨강)

        while (!q.isEmpty()) {
            Node cur = q.poll();
            int curColor = colors[cur.num];

            for (int next : list[cur.num]) {
                if (colors[next] == 0) { // 방문하지 않은 정점이면
                    colors[next] = -curColor; // 현재 정점과 반대 색상으로 칠함
                    q.add(new Node(next, !cur.color));
                } else if (colors[next] == curColor) { // 인접 정점이 같은 색이면 이분 그래프 X
                    return false;
                }
            }
        }
        return true;
    }

    // 문자열을 정수로 변환하는 함수
    static int stringToInteger(String s) {
        return Integer.parseInt(s);
    }
}

 

 

🔍 코드 설명

 

📌 1. 그래프 입력 및 초기화

ArrayList<Integer>[] list = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
    list[i] = new ArrayList<>();
}

for (int i = 0; i < E; i++) {
    StringTokenizer stLogic = new StringTokenizer(br.readLine());
    int a = stringToInteger(stLogic.nextToken());
    int b = stringToInteger(stLogic.nextToken());

    list[a].add(b);
    list[b].add(a);
}

• 인접 리스트(list[])를 사용하여 그래프를 저장

• 무방향 그래프이므로 양쪽(list[a].add(b) & list[b].add(a))을 추가

 

📌 2. 모든 정점에 대해 BFS 실행

int[] colors = new int[N + 1]; // 0: 미방문, 1: 빨강, -1: 파랑

for (int i = 1; i <= N; i++) {
    if (colors[i] == 0) { // 아직 방문하지 않은 정점
        if (!BFS(i, list, colors)) return "NO\n";
    }
}

• 모든 정점(1 ~ N)을 확인하며 방문하지 않은 정점에서 BFS 실행

• BFS 실행 결과가 false이면 이분 그래프가 아니므로 “NO” 출력

 

📌 3. BFS를 사용한 이분 그래프 판별

Queue<Node> q = new ArrayDeque<>();
q.add(new Node(start, true));
colors[start] = 1; // 시작 정점을 1 (빨강)으로 설정

while (!q.isEmpty()) {
    Node cur = q.poll();
    int curColor = colors[cur.num];

    for (int next : list[cur.num]) {
        if (colors[next] == 0) { // 방문하지 않은 정점이면
            colors[next] = -curColor; // 반대 색상으로 칠함
            q.add(new Node(next, !cur.color));
        } else if (colors[next] == curColor) { // 인접 정점이 같은 색이면 이분 그래프 X
            return false;
        }
    }
}

• 큐(Queue)를 사용하여 BFS 탐색

• 각 정점을 두 개의 색(1, -1)으로 칠하면서 진행

• 이미 칠해진 인접 정점이 같은 색이면 이분 그래프가 아님

 

🏆 정리

 

✅ 핵심 포인트

 

✔ BFS를 사용하여 이분 그래프 판별

✔ 정점 방문 시 두 개의 색으로 칠하며 탐색

✔ O(N + E)의 시간 복잡도로 빠르게 해결 가능

 

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!