백준 1707번: 이분 그래프

문제 설명

• https://www.acmicpc.net/problem/1707
• 이분 그래프가 가능한지 판단하는 문제입니다.

접근법

• 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프 입니다.
  

[이미지 및 설명 출처: https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html]

• 이분 그래프는 모든 접점이 반드시 연결되어 있어야 하는 건 아닙니다.

  • 위 그림의 첫번째 예시가 그 경우입니다.

• 방문배열을 boolean이 아닌 int로 설정했습니다.

  • 0: 아직 방문하지 않음
  • 1: 빨간색
  • -1: 검정색

• BFS의 depth가 같은 노드끼리는 모두 같은 색(방문배열의 값)을 공유하고 있어야 합니다.

• BFS의 다음 depth는 현재 depth와 다른 색을 가져야 합니다.

  • 다음 방문위치가 이미 자신과 동일한 색으로 채워져 있다면 이분 그래프가 될 수 없습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] v;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());

		for (int k = 0; k < K; k++) {
			
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			v = new int[V+1];
			HashMap<Integer,List<Integer>> graph = new HashMap<Integer,List<Integer>>();
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				if(graph.containsKey(a)) {
					graph.get(a).add(b);
				}else {
					List<Integer> temp = new LinkedList<Integer>();
					temp.add(b);
					graph.put(a, temp);
				}
				
				if(graph.containsKey(b)) {
					graph.get(b).add(a);
				}else {
					List<Integer> temp = new LinkedList<Integer>();
					temp.add(a);
					graph.put(b, temp);
				}			
			}
			
			boolean answer = true;
			for (int i = 1; i <= V; i++) {
				if(v[i] == 0) {
					if(BFS(i,V,graph)) continue;
					answer = false;
					break;
				}
			}
			if(answer) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
		
	}
	
	public static boolean BFS(int start,int V, HashMap<Integer,List<Integer>> graph) {
		Queue<Integer> q = new LinkedList<Integer>();
		v[start] = 1; // 처음은 빨간색(1)으로 시작
		q.add(start);
		int cnt = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			while(--size>=0) {
				int now = q.poll();
				int flag = (cnt%2 ==0)?1:-1; // flag는 현재의 색
				if(!graph.containsKey(now)) continue; //null pointer 방지
				for (Integer candidate : graph.get(now)) {
					if(v[candidate] == 0) {
						v[candidate] = flag*-1; // 다음 색은 현재의 색과 반대
						q.add(candidate);
					}else if(v[candidate] == flag) return false; // 다음 위치가 이미 현재의 색과 동일한 색으로 채워져 있다면 이분그래프가 아님
				}				
			}			
			cnt ++;
		}
		return true;
	}
}