백준 1707 - 이분 그래프

Java

1707 번 - 이분 그래프

문제

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

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

접근 방법

이분 그래프의 개념을 묻고, 이를 판별하는 문제였다.
이분 그래프는 한마디로, 그래프의 노드를 절반씩 나누어 이 노드들 끼리는 한번에 연결되지 않고 반대편 절반 노드를 거쳐야만 도달하는 그래프를 뜻한다.

노드간의 간선 리스트를 2차원 ArrayList로 표현하였다.
그리고 노드의 색과 방문 여부를 함께 나타내는 1차원 배열을 선언하고, -1로 초기화 한다.

이제 한 점을 방문하여, 연결 되는 노드들의 색을 칠하고 이분 그래프인지 판별한다.

1. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.
2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.
3. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
   BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.
4. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.

한번 BFS를 돈 이후에, 아직 방문하지 노드가 있을 수 있으므로, 다시 한번 노드들을 탐색해 방문하지 않았으면 BFS에 그 노드 값을 넣어 이분 그래프인지 판별한다.

코드

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

public class Main {
	static int v,e, tc;
	static int[] vColor;
	static List<List<Integer>> node;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	tc = stoi(br.readLine());
    	
    	for(int idx = 0; idx < tc; idx++) {
    		boolean isBinary = true;
    		stk = new StringTokenizer(br.readLine());
    		v = stoi(stk.nextToken());
    		e = stoi(stk.nextToken());
    		
    		node = new ArrayList<>();
    		
    		for(int i = 0; i <= v; i++) {
    			node.add(new ArrayList<>());
    		}
    		
    		int from = 0, to;
    		for(int i = 0; i < e; i++) {
    			stk = new StringTokenizer(br.readLine());
    			from = stoi(stk.nextToken());
    			to = stoi(stk.nextToken());
    			node.get(from).add(to);
    			node.get(to).add(from);
    		}
    		
    		vColor = new int[v+1];
    		Arrays.fill(vColor, -1);		// 방문하지 않은 노드를 -1로 표현한다
    		
    		isBinary = BFS(from);			// 한번 이분 그래프인지 탐색한다
    		
    		for(int i = 1; i <= v; i++) {
    			if(vColor[i] == -1) {		// 아직 방문하지 않은 노드들을 다시 방문한단
    				if(!BFS(i)) {
    					isBinary = false;
    					break;
    				}
    			}
    		}
    		
    		if(isBinary)
    			System.out.println("YES");
    		else
    			System.out.println("NO");
    	}
    	
    	br.close();
	}
	
	static boolean BFS(int from) {
		boolean isBinary = true;
		Queue<Vertex> queue = new LinkedList<Main.Vertex>();
		// false가 색 0, true가 색 1
		queue.add(new Vertex(from, false));
		vColor[from] = 0;
		
		int curN, curC;
		Vertex curV;
		end: while(!queue.isEmpty()) {
			curV = queue.poll();
			curN = curV.node;
			curC = curV.color ? 0 : 1;		// 정점의 색, 현재 색과 반대 색을 넣는다.
			
			for(int next : node.get(curN)) {
				if(vColor[next] == -1) {			// 아직 방문하지 않은 노드이면
					vColor[next] = curC;
					queue.add(new Vertex(next,!curV.color));
				}
				else {
					if(vColor[next] != curC) {		// 방문 했는데, 현재 노드 색과 같으면
						isBinary = false;			// 이분 그래프가 아니다
						break end;
					}
				}
			}
		}
		
		return isBinary;
	}
	
	static class Vertex{	// 각 노드의 상태
		int node;
		boolean color;
		
		public Vertex(int node, boolean color) {
			super();
			this.node = node;
			this.color = color;
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

이분 그래프를 배울 수 있었던 문제.
참고한 포스트 : [알고리즘] 이분 그래프(Bipartite Graph)란

개선할 점

없습니다.