2색 칠하기

2색 칠하기

 

문제

---

2색 칠하기란, 다음 두 조건을 만족하면서 그래프의 정점을 모두 색칠할 수 있는지 묻는 문제이다.

1. 2개의 색이 존재한다.

2. 인접한 두 정점은 색깔이 다르다.

   그래프가 주어질 때, 2색 칠하기가 가능한지 출력하는 프로그램을 작성하시오. 예를 들어, 아래의 그래프는 2색 칠하기가 가능한 그래프이며, 정점을 색칠한 결과는 다음과 같다.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다.  

출력

---

주어진 그래프에 대하여 2색 칠하기를 할 수 있으면 YES, 할 수 없으면 NO를 출력한다.

 

예제 입력

9 10
0 1
0 2
0 3
1 5
2 5
3 4
5 6
5 8
6 7
7 8

예제 출력

YES

 

예제 입력

9 11
0 1
0 2
0 3
1 5
2 5
3 4
4 5
5 6
5 8
6 7
7 8

예제 출력

NO

코드 / bfs(사실상)

//2색 칠하기

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

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c = 0;
        int d = 0;
        Queue<Node> q = new LinkedList<>();

        a = sc.nextInt();

        for (int i = 0; i < a; i++) {
            Node node = new Node(i);
            box.add(node);
        }

        b = sc.nextInt();

        for (int i = 0; i < b; i++) {
            c = sc.nextInt();
            d = sc.nextInt();
            box.get(c).getNodes().add(box.get(d));
        }

        q.offer(box.get(0));
        if (canColor(q)) System.out.println("YES");
        else System.out.println("NO");
    }

    public static boolean canColor(Queue<Node> q) {
        Node node;
        ArrayList<Node> datas;

        while (!q.isEmpty()) {
            node = q.poll();
            datas = node.getNodes();

            for (Node data :
                    datas) {
                if (!data.isChecked()) {
                    q.offer(data);
                    data.setColor(!node.isColor());
                    data.setChecked(true);
                } else {
                    if (node.isColor() == data.isColor()) return false;
                }

            }
        }

        return true;
    }


}


class Node {


    private boolean color;
    private boolean isChecked;
    private int data;
    private ArrayList<Node> nodes;

    public boolean isColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }


    public boolean isChecked() {
        return isChecked;
    }

    public void setChecked(boolean checked) {
        isChecked = checked;
    }

    public Node(int data) {
        this.setChecked(false);
        this.data = data;
        nodes = new ArrayList<>();
    }

    public ArrayList<Node> getNodes() {
        return nodes;
    }

}