쌉쌀한 무화과의 개발로그

[문제]

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

[입력]

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

[출력]

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

[예제]

>문제 풀이

 이분 그래프가 뭔지 찾아보다가 정답 코드를 읽어버렸다....^^;;
아마 정답코드를 보지 않았다면, 나는 인접행렬로 먼저 풀었을 것 같다.

근데 인접행렬로 풀면 메모리 초과가 난다고 한다.

이분 그래프란?

이렇게 각 포인트를 두 가지 색상으로 색칠한다고 할 때, 인접한 두 포인트(노드)의 색상이 다른 그래프를 말한다.

*풀이는 사실, 저도 겨우 이해한 것 같고 아래 블로그의 코드를 많이 참고했기 때문에...
아래 블로그를 참고하기 바랍니다.

toastfactory.tistory.com/115

>전체 코드

import java.util.*;

public class Main {
	static int K, V, E;
	static String answer;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] set;
	
	public static void main(String [] args) {
		int p1, p2;
		
		Scanner scan= new Scanner(System.in);
		
		K= scan.nextInt();
		
		while(K-->0) {
			answer= "YES";
			V= scan.nextInt();
			E= scan.nextInt();
			
			graph= new ArrayList<>();
			
			for(int i=0; i<V; i++) {
				graph.add(new ArrayList<>());
			}
			
			for(int i=0; i<E; i++) {
				p1= scan.nextInt()-1;
				p2= scan.nextInt()-1;
				
				graph.get(p1).add(p2);
				graph.get(p2).add(p1);
			}
			
			set= new int[V];
			for(int i=0; i<V; i++) {
				if(set[i]==0) {
					if(!bfs(i)) break;
				}
			}
			System.out.println(answer);
		}//while
		
	}//main
	
	
	public static boolean bfs(int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(n);
		set[n]= 1;
		
		while(!queue.isEmpty()) {
			n= queue.poll();
			for(Integer i: graph.get(n)) {
				if(set[n]==set[i]) {
					answer="NO";
					return false;
				}
				if(set[i]==0) {
					set[i]=set[n]*-1;
					queue.add(i);
				}
			}
		}
		return true;
	}	
}

www.acmicpc.net/problem/1707