#1707 : 이분 그래프

풀이방법

사용된 것:

깊이우선탐색

 

2022.05.25

모든 정점에 1 혹은 2 중에 하나의 번호를 부여해야 한다고 하자.

인접한 두 정점이 같은 번호를 부여받는 일 없이 모든 정점에 1 혹은 2를 부여할 수 있다면

그 그래프는 이분 그래프이다.

여러 칸으로 나누어진 그림을 2가지 색으로만 색칠하되, 인접한 칸끼리는 색이 겹치지 않도록 하는 색칠 수수께끼와 비슷하다고 보면 된다.

이 원리를 이용하여 이 문제를 풀 수 있다. 그 방법은 다음과 같다.

 

1. 정점들을 깊이우선탐색 또는 너비우선탐색하면서, 다음 정점으로 넘어갈 때마다 이전에 방문했던 정점과 다른 번호를 부여한다.
2. 그 후 정점들을 검사해보았을 때, 인접한 두 정점이 같은 번호를 부여받은 경우가 하나도 없다면 이 그래프는 이분 그래프이다.

 

코드

Java(2022.05.25)

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

public class Main {
	
	static ArrayList<Integer>[] arr;	//간선 정보를 저장할 배열
	static int[] givenNumber;		//정점에 부여된 숫자(1 혹은 2가 부여되며, 만약 값이 0이라면 아직 아무 번호도 부여되지 않은 것임)
	static boolean check;	//이분 그래프 여부를 저장할 변수
	
	//정점에 1혹은 2를 부여하는 함수
	static void dfs(int prev, int cur) {
		//이번 정점의 번호가 이미 부여됐다면 return
		if(givenNumber[cur] != 0) return;
		//이번 정점이 시작점이라면 1번을 부여
		if(prev == 0) givenNumber[cur] = 1;
		else {
			//시작점이 아니라면, 이전 정점과 다른 번호를 부여
			int prev_color = givenNumber[prev];	//이전 정점이 부여받은 번호
			if(prev_color == 1) givenNumber[cur] = 2;	//이전 정점이 부여받은 번호가 1번이라면 이번 정점은 2번
			else givenNumber[cur] = 1;	//반대로 이전 정점이 부여받은 번호가 2번이라면 이번 정점은 1번
		}
		//이번 정점과 연결된 모든 정점에 대하여 재귀
		for(int i : arr[cur]) dfs(cur, i);
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int k = Integer.parseInt(br.readLine());
		for(int t = 0; t<k; t++) {
			//정점과 간선의 개수 읽어오기
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			//필요한 변수들 선언 및 초기화
			arr = new ArrayList[v+1];
			for(int i = 1; i<v+1; i++) arr[i] = new ArrayList<Integer>();
			givenNumber = new int[v+1];
			Arrays.fill(givenNumber, 0);
			check = true;

			//간선 정보 읽어와 저장하기
			for(int i = 0; i<e; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr[a].add(b);
				arr[b].add(a);
			}
			
			//숫자 부여하기
			for(int i = 1; i<v+1; i++) {
				dfs(0, i);
			}
			//이분 그래프인지 검사하기
			for(int i = 1; i<v+1; i++) {
				//인접해있는 두 정점이 색이 같은 경우가 발견되면 즉시 check의 값을 false로 바꾸고 검사 종료
				for(int j: arr[i]) {
					if(givenNumber[i] == givenNumber[j]) {
						check = false;
						break;
					}
				}
				if(!check) break;
			}
			//check의 값에 따라 정답 문자열 갱신
			if(check) sb.append("YES"+ System.lineSeparator());
			else sb.append("NO"+ System.lineSeparator());
			
		}
		//정답 출력
		System.out.print(sb);

	}

}