[Java] BOJ1707, 백준 - 이분 그래프

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

1707번: 이분 그래프

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256MB	49704	12781	7530	23.198%

문제

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

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

 

입력

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

 

출력

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

 

제한

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

 

<풀이>

이분 그래프인지 아닌지 판단하기 위해서는 각각의 정점들을 그룹에 따라 분류해주어야 한다.

따라서 int형 group 배열을 만들어주고, 그룹값을 관리하기 편하도록 1그룹과 -1그룹으로 구분한다.

이분 그래프이기 때문에 현재 검사하는 정점과 연결된 정점들은 서로 그룹번호가 달라야 한다.

group값이 0인 경우가 한 번도 방문하지 않은 경우이니, 이 경우에만 이어서 탐색을 한다.

0이 아닌 경우에는 연결된 정점들의 그룹번호가 현재 정점의 그룹번호와 다른지 검사해준다.

 

1. 모든 정점들에 대해서 dfs로 탐색
2. 현재 정점에서 갈 수 있는 모든 정점들을 검사
   1. 만약 한 번도 들린 적 없는 정점이라면(group번호==0)
      1.  그룹번호를 현재 정점의 그룹번호와 반대로 설정해주고 dfs를 계속한다.
   2. 만약 들린 적 있는 정점이라면
      1. 저장되어있는 그룹번호가 현재 정점의 그룹번호와 같은지 비교한다.
         1. 그룹번호가 다르다면 그대로 진행
         2. 그룹번호가 같다면 이분 그래프가 아니므로 flag를 false로 바꿔준다.

 

시간복잡도

인접 리스트를 이용했을 때 DFS는 O(V+E)지만, 이 문제의 경우 이미 지나간 간선이라도 양쪽으로 한 번 더 비교하기 때문에 간선의 탐색 횟수만 2배로 늘려주면 될 것이다.

O(2V+E) = 420,000

 

 

<소스코드>

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

public class Main {

	private static int v;
	private static ArrayList<Integer>[] adj;

	private static int[] group;
	private static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int t = 0; t < k; t++) {
			// 입력부
			StringTokenizer st = new StringTokenizer(br.readLine());
			v = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());

			// 인접리스트
			adj = new ArrayList[v + 1];
			for (int i = 0; i <= v; i++)
				adj[i] = new ArrayList<Integer>();

			for (int i = 0; i < e; i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());
				adj[v1].add(v2);
				adj[v2].add(v1);
			}

			// 어느 그룹인지 저장할 배열
			group = new int[v + 1];

			flag = true;

			for (int i = 1; i <= v; i++) {
				if (group[i] == 0) {
					group[i] = 1;
					dfs(i);
				}
			}
			if (v == 1 || flag)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}

	private static void dfs(int x) {
		for (int i = 0; i < adj[x].size(); i++) {
			// flag가 유효한지 검사
			if (!flag)
				return;
			// 현재 정점은 x
			// 현재 정점의 그룹은 group[x]
			// 그러면 현재 정점에서 연결된 정점들의 그룹은 group[x]와 반대여야 함
			int n = adj[x].get(i); // 연결된 정점

			// 방문한 적 없는 노드라면
			if (group[n] == 0) {
				group[n] = group[x] * (-1);
				dfs(n);
			} else if (group[n] == group[x]) {
				// 만약 방문한 적 있는데 그룹번호가 같으면 false를 return
				flag = false;
			}
		}
	}
}