[JAVA] 백준 1707 - 이분 그래프

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

- 7등에 랭크 되어있는 거 보면 느린코드는 아닌 듯 하다.

 

- 이분 그래프란?

그래프에서 임의의 점을 선택하여 그 점과 이웃하는 다른 점은 선택된 점과 색이 달라야 한다. 그리고 그래프에 칠해진 색은 2종류가 가능할 때 이분 그래프라고 한다.

 

 

예를 들어, 아래는 이분 그래프인가?

 

정답은 이분그래프가 맞다. 왜냐하면 아래처럼 2가지의 색상만을 이용하여 임의의 점을 선택할 시 모든 이웃이 자신과 다른 색을 가졌기 때문이다. 

 

 

 

그렇다면 아래의 그래프는 이분 그래프인가? 정답은 아니다. 1번과 2번 정점의 색이 같기 때문이다. 어떠한 경우의 수를 이용하더라도 성립하지 않는다.

 

 

- 이분 그래프 여부 알고리즘

 

1. 모든 정점을 방문하였는가?

2. 그렇다면 "YES"를 출력하고 프로그램 종료한다.

3. 그렇지 않다면 방문하지 않은 정점을 한 곳 방문하고 빨간색으로 칠한다. (즉 queue에 해당 정점을 푸시한다.) 

  3-1. queue에서 정점하나를 꺼내고 해당 정점과 연결된 모든 정점을 가져온다.

    3-1-1. 연결된 정점이 방문한 적이 있다면 연결된 정점과 현재 정점의 색이 같다면 "NO"를 출력하도록 한다.

    3-1-2. 연결된 정점이 방문한 적이 없다면 현재 정점과 다른 색을 칠하고 queue에 넣는다.

    3-1-3. queue 에 아무것도 없을 때 까지 3-1을 반복한다.

4. 1번으로 간다.

 

- 예시

1. 모든 정점을 방문하지 않았기 때문에 1번 정점을 방문하고 빨간색으로 칠한다. 즉 1번 정점을 큐에 넣는다.

현재 큐상황)  [ 1 ]

 

 

2. 큐에서 1번 정점을 꺼내고 1번과 연결된 3번 정점은 방문한 적이 없기 때문에 파란색으로 칠하고 큐에 넣는다.

현재 큐상황: [ 3 ]

 

 

3. 큐에서 3번 정점을 꺼내고 3번과 연결된 모든 점을 꺼낸다. 1번 정점은 방문한 적이 있지만 3번 정점과 색이 다르므로 통과한다. 2번과 4번 정점은 방문한 적이 없으므로 3번 정점과 다른 색을 칠하고 큐에 넣는다.

현재 큐상황 : [ 2 , 4 ]

 

4. 큐에서 2번을 꺼내고 연결된 정점 3번이 2번 정점과 색이 다르므로 통과. 현재 큐상황 : [ 4 ]

5. 큐에서 4번을 꺼내고 연결된 정점 3번이 4번 정점과 색이 다르므로 통과. 현재 큐상황: []

6. 큐가 비었으므로 BFS 탐색 종료

 

7. 전체 정점 중에서 방문하지 않은 정점 5번 정점를 방문하여 빨간 색으로 칠하고 큐에 5번 정점을 푸시한다.

현재 큐상황 : [5]

 

8. 큐에서 5번정점을 꺼내고 5번 정점과 연결된 모든 점이 방문한 적이 없으므로 다른색을 칠하고 6번 정점과 7번 정점을 큐에 넣는다.

현재 큐상황: [ 6, 7]

 

 

 

 

9. 큐에서 6번 정점을 꺼내고 연결된 모든 점을 확인한다. 그 결과 7번 정점과 색이 같으므로 "NO" 를 출력하고 모든 진행상황을 중단한다.

 

 

 

- 자바 코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


    static int tt;
    static int v,e;
    static Node[] nodes;
    static boolean[] visited;
    static boolean ans;


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        tt = Integer.parseInt(br.readLine());
        while(tt--!=0){
            st = new StringTokenizer(br.readLine());

            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            nodes = new Node[v+1];
            visited = new boolean[20001];

            for(int i=1;i<=v;i++) {
                nodes[i] = new Node(i);
            }

            ans = true;

            // 연결 그래프 설정
            int a,b;
            for(int i=0;i<e;i++){
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());

                nodes[a].child.add(nodes[b]);
                nodes[b].child.add(nodes[a]);
            }

            for(int i=1;i<=v;i++){
                if(!visited[i]){
                    visited[i] = true;
                    nodes[i].setColor(1);
                    if(!bfs(i)){
                        ans = false;
                        break;
                    }
                }
            }

            System.out.println(ans?"YES":"NO");

        }


    }
    static boolean bfs(int idx){
        Queue<Node> q = new LinkedList<>();
        q.add(nodes[idx]);

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

            //check
            if(check(node)){
                return false;
            }
            else{
                for(Node child : node.child){
                    if(!visited[child.idx]){
                        visited[child.idx] = true;
                        child.setColor(1-node.color);
                        q.add(child);
                    }
                }
            }

        }
        return true;

    }

    static boolean check(Node node){
        for(Node temp : node.child){
            if(visited[temp.idx] && temp.color == node.color){
                return true;
            }
        }
        return false;
    }



    static class Node{
        int idx;
        int color;

        ArrayList<Node> child = new ArrayList<>();


        public Node(int idx) {
            this.idx = idx;
        }

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

    }

}