[Baekjoon] 이분 그래프

👀 문제 설명

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

제한

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

 

예제 입력 1

2

3 2

1 3

2 3

4 4

1 2

2 3

3 4

4 2

 

예제 출력 1

YES

NO

 

✍🏻풀이

문제 풀이에 앞서, 이분 그래프는 다음과 같은 그래프이다.

그림과 같이, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 뜻한다.

-> 참고

 

이분 그래프인지 확인하는 방법은 그래프 탐색을 이용해 정점을 방문할 때마다 두 가지 색 중 한 가지를 칠하면 된다.

이 때, 현재 정점에서 인접한 정점으로 이동할 때 다른 색을 칠해줘야 한다!

이렇게 다 칠하고 난 후, 자신과 인접한 정점의 색이 같다면 이분 그래프가 아닌 것이다.

* 주의할 점은 연결 그래프와 비연결 그래프 모두 고려해야 한다는 점이다. 비연결 그래프인 경우에는 모든 정점에 대해 확인해야 한다.

 

위 방법 그대로 문제를 풀면 되는데, 이 문제에서 간선의 개수가 최대 200,000개이므로, 인접 행렬을 사용하면 메모리 초과가 난다.

-> ArrayList 배열로 한 정점과 그에 인접한 정점들을 저장해주면 된다.

ArrayList<Integer>[] graphInfo = new ArrayList[V + 1]; 로 리스트를 생성한 후에, 정보를 저장한다.

예를 들어, 3번 정점이 4, 5번과 연결되어 있다고 가정해보자.

graphInfo[3]은 하나의 ArrayList이고, 이 ArrayList에 4와 5가 차레대로 저장되어 있는 것이다. 즉, graphInfo[3].get(0)은 4, graphInfo[3].get(1)은 5가 될 것이다.

 

이제 DFS와 graphInfo를 사용해서 정점들을 색칠해주고, 정점들을 다 색칠해준 후에 다시 정점들을 보면서 인접한 정점들이 같은 색인지 확인해주면 된다.

 

코드

package boj;

// 이분 그래프 (https://www.acmicpc.net/prAroblem/1707 )

import java.util.*;
import java.io.*;

public class BOJ_1707 {
	
	private static int V, E; // 정점의 개수 V와 간선의 개수 E 변수를 선언한다.
	private static ArrayList<Integer>[] graphInfo; // 간선 연결 정보 저장 -> 이차원 배열로 하면 메모리 초과 남!!!!
	
	private static int[] color;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력받기 위해 BufferedReader 객체 생성
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력하기 위해 BUfferedWriter 객체 생성
		StringTokenizer st; // 공백을 기준으로 입력받아오기 위해 StringTokenizer 객체 선언
		
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수를 입력받는다.
		for (int tc = 0; tc < T; tc++) { // 각 테스트케이스마다 실행 & 출력
			st = new StringTokenizer(br.readLine()); // 공백을 기준으로 입력받아오기 위해 StringTokenizer 객체 생성
			
			V = Integer.parseInt(st.nextToken()); // V 값을 받아온다.
			E = Integer.parseInt(st.nextToken()); // E 값을 받아온다.
			color = new int[V + 1];
			graphInfo = new ArrayList[V + 1];
			
			for (int i = 0; i < E; i++) { // 간선에 대한 정보들을 입력받는다.
				st = new StringTokenizer(br.readLine()); // 공백을 기준으로 입력받아오기 위해 StringTokenizer 객체 생성
				
				int u = Integer.parseInt(st.nextToken()); // 시작 정점 정보를 받아온다.
				int v = Integer.parseInt(st.nextToken()); // 끝 정점 정보를 받아온다.
				
				// 연결된 정보를 저장해준다.
				if (graphInfo[u] == null) {
					graphInfo[u] = new ArrayList<>();
				}
				graphInfo[u].add(v);
				
				if (graphInfo[v] == null) {
					graphInfo[v] = new ArrayList<>();
				}
				graphInfo[v].add(u);
			}
			
			for (int i = 1; i <= V; i++) {
				if (graphInfo[i] != null && color[i] == 0) { // 1번 정점부터 출발하여, 가능한 정점들을 모두 방문한다.
					connected(i, 1);
				}
			}
			
			// 이분 그래프가 맞는지 확인
			boolean poss = isPossible();
			
			bw.write((poss == true ? "YES\n" : "NO\n")); // conn이 true라면, 모든 정점들이 이어져있으므로, 이분 그래프가 아니다. (NO 출력) / false라면, 이분 그래프이므로 YES 출력
		}
		
		bw.flush(); // 출력 스트림에 쌓인 애들을 내보내준다.
		bw.close(); // BufferedWriter를 다 썼다면 close 해준다.
	}
	
	// 이분 그래프가 맞는지 확인 -> 인접한 정점들이 같은 색상이면 이분 그래프가 아니다.
	private static boolean isPossible() {
		for (int v = 1; v <= V; v++) {
			if (graphInfo[v] != null) {
				for (int i = 0; i < graphInfo[v].size(); i++) {
					if (color[v] == color[graphInfo[v].get(i)]) {
						return false;
					}
				}
			}
		}
		
		return true;
	}
	
	// DFS를 활용해 방문 가능한 정점들을 모두 방문하는 메서드
	private static void connected(int cur, int c) { // visited는 정점들이 방문한 것들인지 저장하는 배열, cur은 현재 정점이 몇 번인지 저장하는 변수
		color[cur] = c; // 현재 정점 방문 표시 & 색 칠해줌
		
		// 현재 정점과 연결된 정점들 찾기
		for (int i = 0; i < graphInfo[cur].size(); i++) {
			int next = graphInfo[cur].get(i);
			
			if (color[next] == 0) { // 인접한 정점이 아직 방문하지 않은 곳이라면 해당 정점으로 이동 
				connected(next, 3 - c); // 현재와 다른 색으로 칠해준다.
			}
		}
	}

}