[백준1707] 이분 그래프 [java]

---

이 문제를 풀기 위해서 이분 그래프가 무엇인지 먼저 공부할 필요가 있었다!!

정말 쉽게!!

한 노드의 색깔이 빨간색이라고 하면 그와 연결된 노드들의 색깔은 파란색인 것이다.

하지만 그 파란색 노드들끼리는 연결되면 안된다.

즉 연결된 노드들은 서로 색깔이 달라야 하는 것이다.

 

나는 이 문제를 dfs를 이용해서 풀었다.

또한 방문했는지는 배열을 만들어 0,1,2을 입력해서 방문여부를 확인했다

0인 경우에는 방문 x, 1인 경우에는 part1, 2인 경우에는 part2인 것으로 만들었다.

dfs메소드를 이용하여 모든 노드들의 part를 정하고

마지막에 연결된 노드인데 part가 같은 경우 "NO"를 출력하도록 했다.

 

코드

package baekjoon;

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

public class bipartite_graph {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt(); // 정점의 수
            int m = sc.nextInt(); // 간선의 수

            ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];

            // 정점만큼 리스트 생성
            for(int i = 1; i<=n;i++){
                a[i] = new ArrayList<>();
            }

            for(int i = 0; i<m; i++){
                int part1 = sc.nextInt();
                int part2 = sc.nextInt();

                a[part1].add(part2);
                a[part2].add(part1);
            }

            // 정점의 방문 여부 0 : 방문 x , 1 : part1방문 2 : part2방문
            int[] color = new int[n+1];

            boolean ok = true;

            for(int i = 1; i<=n; i++){
                if(color[i] == 0){
                    dfs(a,color,i,1);
                }
            }
            for(int i = 1; i<=n;i++){
                for(int j : a[i]){
                    if(color[i] == color[j]){
                        ok = false;
                    }
                }
            }
            if(ok){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }

    private static void dfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
        color[x] = c;
        for(int y : a[x]){
            if(color[y] == 0){
                dfs(a,color,y,3-c);
            }
        }
    }
}