[BOJ 1707] 이분 그래프 (Java)

문제

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

풀이

이분 그래프 개념을 알아야 풀 수 있다. 

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

문제의 예제를 살펴보자. 

EX1)

V = 3 , E= 2
1 3
2 3

아래와 같이 이분 그래프를 만들 수 있다.

 

EX1

EX2)
V = 4 , E= 4
1 2
2 3
3 4
4 2

 

2번과 3번이 서로 다른 색을 가진 꼭지점을 가진 변으로 연결되어있다고 가정하면, 

4번은 어떤 색을 칠해도 이분 그래프에 만족하지 않는다. 

아래 그림에서,  4번이 파란색으로 칠해지면 2번과 4번은 동일한 색으로 연결되므로 이분그래프 조건에 충족되지 않는다. 반대로 4번이 빨강색으로 칠해지면 3번과 4번은 동일한 색으로 연결되므로 이분그래프 조건에 충족되지 않는다.

그래서 해당 케이스의 답은 "NO"이다.

 

 

EX2

 

 

질문 게시판에서 찾은 반례로, 아래와 같이 모든 정점이 연결되어 있지 않은 케이스가 있다. 

즉, 한 번의 BFS로 모든 정점을 탐색할 수 없는 경우에는 

남은 미방문 정점에 대해 다시 BFS를 수행해 줘야 한다. 

1
5 4
1 2
3 4
4 5
3 5

BFS를 진행하며 RED, BLUE를 번갈아가며 방문체크 변수에 저장해나간다. 

만약 이미 방문한 노드인데 이전 노드와 색이 동일하다면 "NO"를 리턴한다. 

 

소스코드

package bfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1707 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            bw.write(solution(V, E, br) + "\n");
        }
        bw.flush();
    }

    public static String solution(int V, int E, BufferedReader br) throws Exception{
        // 인접 정보 담을 자료구조 선언
        ArrayList<Integer>[] adjs = new ArrayList[V+1];
        for(int i = 1; i <= V; i++){
            adjs[i] = new ArrayList<Integer>();
        }

        // 인접 정점 정보 저장
        StringTokenizer st = null;
        for(int i = 0; i < E; i ++){
            st = new StringTokenizer(br.readLine());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());
            adjs[nodeA].add(nodeB);
            adjs[nodeB].add(nodeA);
        }

        // bfs
        // 모든 정점이 연결되어 있는 것이 아님.
        // 모든 탐색 결과가 YES 여야 YES 리턴
        // 하나라도 NO가 있을 경우 NO 리턴
        String[] visited = new String[V+1];
        for(int i = 1; i <= V; i++){
            if(visited[i] != null) continue;
            if("NO".equals(bfs(i, adjs, visited, V))){
                return "NO";
            };
        }

        return "YES";
    }

    public static String bfs(int start, ArrayList<Integer>[] adjs, String[] visited, int V){
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(start);
        visited[start] = "RED";

        while(!que.isEmpty()){
            int now = que.poll();
            String nowColor = visited[now];
            String adjColor = "RED".equals(nowColor) ? "BLUE" : "RED";
            for(Integer adj : adjs[now]){
                if(visited[adj] != null) {
                    if(nowColor.equals(visited[adj])){
                        return "NO";
                    }
                    continue;
                }
                visited[adj] = adjColor;
                que.offer(adj);
            }
        }
        return "YES";
    }
}