[BOJ/백준] 1707번 이분 그래프 (JAVA/자바) - DFS

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

1707번: 이분 그래프

 

풀이

 

1. ArrayList 배열을 만들어 graph 입력을 받는다 (양방향)

			graph = new ArrayList[V + 1];
			for (int i = 0; i <= V; i++) {
				graph[i] = new ArrayList<>();
			}
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				graph[u].add(v);
				graph[v].add(u);
			}

 

2. 인접한 노드들은 서로 다른 색을 가지고 있어야 하므로 (Red, Blue) 파이널 상수 선언을 해둔다

	static final int RED = 1;
	static final int BLUE = -1;

 

3. dfs() 탐색

	public static void dfs(int vertex, int color) {
		colors[vertex] = color;
		
		for(int v : graph[vertex]) {
			if(colors[v]==colors[vertex]) {
				flag = false;
				return;
			}else if(colors[v]==0) {
				dfs(v, -color);
			}
		}
	}

(1) 인접한 노드가 같은 색인지 아닌지 확인 -> 같은 색이면 이분 그래프가 아니므로 flag를 false로 바꿔준다.

(2) 방문한 노드가 아니었다면, 그 노드의 색깔을 현재 노드와 반대되는 색으로 정해준다. (방문체크와 비슷)

 

4. 노드들의 집합마다 이분 그래프인지 확인해야 하므로 모든 정점을 돌며 체크한다.

			flag = true;
			colors = new int[V+1];
			for(int i=1; i<=V; i++) {
				if(colors[i]==0) {
					dfs(i, RED);
				}
				if(!flag) break;
			}

- dfs안에서 현재 집합이 이분 그래프가 아님이 판별 났으면 반복문을 중간에 멈춤.

 

최종 코드

package bdfs;

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

public class BOJ_1707_이분그래프 {
	static int K, V, E;
	static ArrayList<Integer>[] graph;
	static boolean flag;
	static int colors[];
	static final int RED = 1;
	static final int BLUE = -1;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		while (K-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			graph = new ArrayList[V + 1];
			for (int i = 0; i <= V; i++) {
				graph[i] = new ArrayList<>();
			}
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				graph[u].add(v);
				graph[v].add(u);
			}
			flag = true;
			colors = new int[V+1];
			for(int i=1; i<=V; i++) {
				if(colors[i]==0) {
					dfs(i, RED);
				}
				if(!flag) break;
			}
			if(flag) System.out.println("YES");
			else System.out.println("NO");
		}

	}

	public static void dfs(int vertex, int color) {
		colors[vertex] = color;
		
		for(int v : graph[vertex]) {
			if(colors[v]==colors[vertex]) {
				flag = false;
				return;
			}else if(colors[v]==0) {
				dfs(v, -color);
			}
		}
	}
}