[백준(Baekjoon)][자바(java)] 1707 : 이분 그래프 / 그래프와 순회

 

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine()), V, E, u, v, i;
		StringTokenizer st;
		List<List<Integer>> edge;
		Queue<Integer> queue; // vertex num
		int visited[], flag, flag_cur, flag_next; // 0 : not visited, 1 & -1 : flag
		StringBuilder sb = new StringBuilder();
		loop:
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			edge = new ArrayList<>();
			for (i = 0; i < V; ++i)
				edge.add(new ArrayList<>());
			for (i = 0; i < E; ++i) {
				st = new StringTokenizer(br.readLine());
				u = Integer.parseInt(st.nextToken()) - 1;
				v = Integer.parseInt(st.nextToken()) - 1;
				edge.get(u).add(v);
				edge.get(v).add(u);
			}
			queue = new ArrayDeque<>();
			visited = new int[V];
			for (i = 0; i < V; ++i) {
				if (visited[i] == 0) {
					queue.add(i);
					visited[i] = 1;
					while (!queue.isEmpty()) {
						u = queue.remove();
						flag_cur = visited[u];
						flag_next = flag_cur * -1;
						for (int vv : edge.get(u)) {
							flag = visited[vv];
							if (flag == 0) {
								queue.add(vv);
								visited[vv] = flag_next;
								continue;
							}
							if (flag == flag_cur) {
								sb.append("NO\n");
								continue loop;
							}
						}
					}
				}
			}
			sb.append("YES\n");
		}
		br.close();
		System.out.println(sb.toString());
	}
}

 

< 이분 그래프 >

• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프
• 모든 꼭짓점(정점)을 빨강과 파랑으로 색칠하되, 모든 변(간선)이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프
  (인접한 정점끼리 다른 색으로 칠함)

정점을 방문했는지 체크하는 배열( visited[] )에서 boolean 타입 대신 int 타입으로 선언하여 세 가지 상태를 나타냄

• 0 : not visited
• 1, -1 : flag

모든 정점을 탐색하면서
현재 정점에 1을 지정한다면
인접한 다음 정점들에 -1를 지정한다

단, 인접한 정점들 중 이미 방문 되어 있고 현재 정점의 flag와 같으면
이분 그래프의 조건에 부합하지 않는다