[백준 1707번] 이분 그래프 (java)

사용한 방법 : BFS, DFS

 

어려웠던 점 : 

처음에는 graph를 나타낼때 인접행렬을 사용하여 나타냈었는데 계속 메모리 초과가 났다.

그래서 ArrayList<ArrayList<Integer>> graph=new ArrayList<>();로 바꾸어서 해결하였다. 평소에 bfs, dfs 문제를 풀 때는 인접행렬을 이용하여 풀었기 때문에 리스트를 이용한 풀이가 낯설었다.

인접행렬의 경우, 두 정점이 인접할 경우 1을 넣고, 인접하지 않은 경우 0을 넣는 방식이다.

리스트를 사용하면 0번째 리스트에서는 정점 1과 인접한 정점들의 번호가 들어가고, 1번째 리스트에서는 정점 2와 인접한 정점들의 번호가 들어가는 식이다. 리스트를 사용하면 인접한 정점들에 대한 정보만 들어가기 때문에 메모리가 더 적게 차지한다.

 

즉, 메모리면에서는 행렬보다는 리스트가 더 효율적인 것을 알 수 있다.

 

풀이 내용 : 

그리고 처음에는 color배열과 isvisited배열을 두어서 문제를 물었는데, color배열 하나만으로도 두가지 색은 1과-1로 나타내고 아직 방문하지 않은 정점은 색이 없다고 하여 0으로 나타나면 isvisited배열을 굳이 만들 필요가 없어지게 된다.

 

이분 그래프는 인접한 정점이 서로 다른 색이면 이분 그래프이다.

 

이분 그래프인지를 판별하는 방법은

1. 그래프 탐색을 하면서 인접한 정점은 서로 다른 색(1 혹은 -1)을 칠한다.

2. 반복문을 통해서 각 정점마다 돌면서 color가 0인 정점을 찾아 탐색을 다시 해줘야 한다. 

   비연결 그래프인 경우도 고려해야하기 때문이다.

3. 탐색을 모두 마친 후, 인접한 두 정점이 하나라도 같은 색이면 이분 그래프가 아니다.

 

BFS 전체 코드 

package num1707;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Main {

	static ArrayList<ArrayList<Integer>> graph;
	static int[] color;
	static int V, E;
	static Stack<Integer> s = new Stack<>();

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int i = 0; i < K; i++) {
			String[] s = br.readLine().split(" ");
			V = Integer.parseInt(s[0]);
			E = Integer.parseInt(s[1]);

			color = new int[V];
			graph = new ArrayList<>();
			for (int j = 0; j < V; j++) {
				graph.add(new ArrayList<>());
			}

			for (int e = 0; e < E; e++) {
				s = br.readLine().split(" ");
				int a = Integer.parseInt(s[0]);
				int b = Integer.parseInt(s[1]);

				graph.get(b - 1).add(a - 1);
				graph.get(a - 1).add(b - 1);

			}

			for (int j = 0; j < V; j++) {
				if (color[j] == 0) {
					color[j] = 1;
					dfs(V, j);
				}
			}

			bw.write(check(V) + "\n");
		}
		bw.flush();
	}

	public static void dfs(int V, int start) {

		s.push(start);

		while (!s.isEmpty()) {
			int v = s.pop();
			int c = color[v];

			for (int i = 0; i < graph.get(v).size(); i++) {

				int v2 = graph.get(v).get(i);

				if (color[v2] == 0) {
					if (c == 1)
						color[v2] = -1;
					else if (c == -1)
						color[v2] = 1;

					dfs(V, v2);
				}
			}
		}
	}

	public static String check(int V) {

		for (int n = 0; n < V; n++) {
			for (int m = 0; m < graph.get(n).size(); m++) {
				if (color[n] == color[graph.get(n).get(m)]) {
					return "NO";
				}
			}
		}
		return "YES";
	}
}

DFS 전체 코드 

package num1707_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static ArrayList<ArrayList<Integer>> graph;
	static int[] color;
	static int V, E;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int i = 0; i < K; i++) {
			String[] s = br.readLine().split(" ");
			V = Integer.parseInt(s[0]);
			E = Integer.parseInt(s[1]);

			color = new int[V];
			graph = new ArrayList<>();

			for (int j = 0; j < V; j++)
				graph.add(new ArrayList<>());

			for (int e = 0; e < E; e++) {
				s = br.readLine().split(" ");
				int a = Integer.parseInt(s[0]);
				int b = Integer.parseInt(s[1]);

				graph.get(b - 1).add(a - 1);
				graph.get(a - 1).add(b - 1);
			}

			for (int j = 0; j < V; j++) {
				if (color[j] == 0) {
					color[j] = 1;
					bfs(V, j);
				}
			}
			bw.write(check(V) + "\n");
		}
		bw.flush();
	}

	public static void bfs(int V, int start) {

		Queue<Integer> q = new LinkedList<>();

		q.offer(start);

		while (!q.isEmpty()) {
			int v = q.poll();
			int c = color[v];

			for (int i = 0; i < graph.get(v).size(); i++) {

				int v2 = graph.get(v).get(i);

				if (color[v2] == 0) {
					if (c == 1)
						color[v2] = -1;
					else if (c == -1)
						color[v2] = 1;

					q.offer(v2);
				}
			}
		}
	}

	public static String check(int V) {

		for (int n = 0; n < V; n++) {
			for (int m = 0; m < graph.get(n).size(); m++) {
				if (color[n] == color[graph.get(n).get(m)]) {
					return "NO";
				}
			}
		}
		return "YES";
	}
}