[백준] 1707번 : 이분 그래프

문제

 

 

접근 방식

이분 그래프의 개념만 알면 BFS나 DFS로 쉽게 풀 수 있는 문제다.

 

 

위와 같은 그래프가 주어졌을 때 DFS 탐색 순서는 아래와 같다.

1 > 2 > 3 > 4 > 2 > 4

 

이분 그래프는 모든 정점을 두 가지 색으로만 칠할 수 있다고 생각하면 되는데

인접한 정점을 방문할 때마다 현재 정점과 반대되는 색깔로 칠하다

만약 다음에 방문할 정점이 이미 색이 칠해져있고 현재 정점과 색깔이 같다면

이분 그래프가 아니라는 것을 알 수 있다.

1번 정점 방문 => 1번 정점 빨간색으로 색칠
2번 정점 방문 => 2번 정점 파란색으로 색칠
3번 정점 방문 => 3번 정점 빨간색으로 색칠
4번 정점 방문 => 4번 정점 파란색으로 색칠
2번 정점 방문 => 2번 정점 빨간색으로 색칠 (이미 파란색인데 빨간색으로 칠할 수 없음)

== 이분 그래프가 아님

 

위와 같은 순서로 진행된다.

 

DFS로 풀었는데 인접 정점 방문하며 색칠하는거라 BFS로 푸는게 더 효율적일거 같다

 

풀이

public class Main {

	private static int v, e, x, y;
	private static ArrayList<ArrayList<Integer>> near;
	private static int[] paint;

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

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());

			v = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());

			near = new ArrayList<>();
			paint = new int[v + 1];
			boolean isBipartite = true;

			for (int i = 0; i <= v; i++) {
				near.add(new ArrayList<>());
			}

			while (e-- > 0) {
				st = new StringTokenizer(br.readLine());

				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());

				near.get(x).add(y);
				near.get(y).add(x);
			}

			for (int i = 1; i <= v; i++) {
				if (paint[i] != 0) continue;
				if (!dfs(i, -1)) {
					isBipartite = false;
					break;
				}
			}

			if (isBipartite) sb.append("YES").append("\n");
			else sb.append("NO").append("\n");
		}

		System.out.println(sb);
	}

	private static boolean dfs(int cur, int prev) {
		int color = -(prev);
		paint[cur] = color;

		for (int next : near.get(cur)) {
			if (paint[next] == color) return false;
			else if (paint[next] == -color) continue;
			if (!dfs(next, color)) return false;
		}

		return true;
	}
}