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

BOJ 1707 이분 그래프

문제풀이

처음에 이분 그래프의 의미를 잘못 이해해서 시간이 조금 걸린 문제다. 이분 그래프는 그래프의 정점을 두 그룹으로 나누었을 때 같은 그룹에 속한 정점끼리는 인접하지 않는 것이다. 따라서 그래프를 탐색하는 과정에서 현재 정점과 다음 정점의 그룹이 다르면 된다. 그래프의 탐색은 DFS, BFS 모두 가능하며 나는 DFS로 구현하였다.

• 그룹은 색상으로 나타내었다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static final int RED = 1;
	static final int BLUE = -1;
	static ArrayList<ArrayList<Integer>> adj;
	static int[] colors;
	static int K, V, E;
	static boolean ans;

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

		K = stoi(br.readLine());

		for (int k = 0; k < K; ++k) {
			st = new StringTokenizer(br.readLine());

			V = stoi(st.nextToken());
			E = stoi(st.nextToken());

			ans = true;
			colors = new int[V + 1];
			adj = new ArrayList<>();
			for (int i = 0; i < V + 1; ++i) {
				adj.add(new ArrayList<>());
			}

			// 인접리스트 초기화 
			for (int i = 0; i < E; ++i) {
				st = new StringTokenizer(br.readLine());
				int from = stoi(st.nextToken());
				int to = stoi(st.nextToken());

				// 무방향 그래프
				adj.get(from).add(to);
				adj.get(to).add(from);
			}

			for (int i = 1; i < V + 1; ++i) {
				if(colors[i] == 0) {
					if(dfs(i, RED)) break;
				}
			}
			System.out.println(ans ? "YES" : "NO");
		}
	}
	
	private static boolean dfs(int start, int color) {
		// 현재 정점 색칠하기
		colors[start] = color;

		for (Integer i : adj.get(start)) {
			// 인접 정점의 색이 같으면 이분 그래프가 아니며 함수를 바로 끝내도록 한다.
			if (colors[i] == color) {
				ans = false;
				return true;
			}

			if (colors[i] == 0) {
				// 아직 방문하지 않았던 정점에 대해서 현재 정점과 다른 색상을 칠한다.
				if (dfs(i, -color))
					return true;
			}
		}
		return false;
	}

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