다시 정리 ! 그래프 문제(bfs,dfs) #1707: 이분 그래프 [JAVA]

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

1707번: 이분 그래프

 

 

---

 

 

 

 

문제 접근

 

 

[ 참고 ]https://www.youtube.com/watch?v=mDSQfb5Rqc4

 

 

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

 

 

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

public class Main {

	static ArrayList<Integer>[] A;
	static int[] check;
	static boolean[] visited;
	static boolean IsEven;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		while (K-- > 0) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			A = new ArrayList[V + 1];
			visited = new boolean[V + 1];
			check = new int[V + 1];
			IsEven = true;

			for (int i = 0; i < V + 1; i++) {
				A[i] = new ArrayList<>();
			}

			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				A[a].add(b);
				A[b].add(a);
			}

			// 모든 노드에서 DFS 실행해야함
			for (int i = 1; i <= V; i++) {
				if (IsEven) { // 이분 그래프인가
					dfs(i);
				} else {
					break; // 이분 그래프가 아닌게 확정되면 반복문 탈출(더 볼 필요 없음.)
				}
			}
			if (IsEven)
				System.out.println("YES");
			else
				System.out.println("NO");
		}

	}

	private static void dfs(int v) {

		visited[v] = true;

		for (int i : A[v]) {
			if (!visited[i]) {
				// 바로 직전에 있는 노드와 다른 집합으로 분류해주기(0 또는 1로)
				check[i] = (check[v] + 1) % 2; // 토글처럼
				dfs(i);
			} else if (check[v] == check[i]) { // 이미 방문한 노드 & 직전 노드와 같은 집합이면
				IsEven = false;
			}
		}
	}
}

 

 

 

 

 

눈 여겨볼 것

 

 

- isEven으로 이분 그래프인지 표시, 이분 그래프가 아닌게 확정되면 더 탐색하지 않고 반복문 탈출

- 인접리스트로 그래프를 표현

- 집합 분류를 %2를 함으로써 토글처럼 한 것.