BOJ01707 이분 그래프

https://www.acmicpc.net/problem/1707 (opens new window)

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프 인지 아닌지 판별한다.

이분 그래프

이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 의미한다.

이분 그래프 (opens new window)

제출 코드

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BOJ1707 {

    private static List<List<Integer>> graph;
    private static int[] team;
    private static boolean isParticiple;

    private static final int RED = 1;

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        team[v] = RED;

        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            // 인접 노드 탐색
            for (Integer i : graph.get(node)) {
                // 이전 팀과 같은 경우
                if (team[node] == team[i]) {
                    isParticiple = false;
                    return;
                }

                if (team[i] == 0) {
                    team[i] = team[node] * -1;
                    queue.add(i);
                }
            }
        }
    }

    private static void dfs(int v, int color) {
        team[v] = color;

        for (Integer i : graph.get(v)) {
            if (team[v] == team[i]) {
                isParticiple = false;
                return;
            }

            if (team[i] == 0) {
                dfs(i, color * -1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();

        while (t-- > 0) {
            int v = scanner.nextInt();
            int e = scanner.nextInt();

            graph = new ArrayList<>();
            for (int i = 0; i <= v; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 0; i < e; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();

                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            team = new int[v + 1];
            isParticiple = true;
            for (int i = 1; i <= v; i++) {
                if (team[i] == 0) {
//                    bfs(i);
                    dfs(i, RED);
                    if (!isParticiple) {
                        break;
                    }
                }
            }

            if (isParticiple) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

#BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색