21.07.28 - [BOJ] 1707. 이분 그래프

[suhyunsim]

문제

• 1707

핵심 아이디어

이분 그래프

• 그래프를 다음과 같이 A와 B로 나눌 수 있으면 이분 그래프라고 함
• A에 포함되어 있는 정점끼리 연결된 간선이 없음
• B에 포함되어 있는 정점끼리 연결된 간선이 없음
• 모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에
• 그래프를 DFS 또는 BFS 탐색으로 이분 그래프인지 아닌지 알아낼 수 있음

풀이

• Color 배열 -> A, B
• 0: 방문 안함, 1: A, 2: B
• DFS -> return true: 이분그래프

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q1707;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        while (k-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<Integer>[] a = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                a[u].add(v);
                a[v].add(u);
            }
            int[] color = new int[n + 1];
            boolean ok = true;
            for (int i = 1; i <= n; i++) {
                if (color[i] == 0) {
                    if (!dfs(a, color, i, 1)) {
                        ok = false;
                    }
                }
            }
            if (ok) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean dfs(ArrayList<Integer>[] a, int[] color, int now, int c) {
        color[now] = c; //c는 1 or 2, node가 c일 때 next는 3 - c
        for (int next : a[now]) {
            if (color[next] == 0) {
                if (!dfs(a, color, next, 3 - c)) return false;
            } else if (color[next] == color[now]) return false;
        }
        return true;
    }
}