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

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

1707번: 이분 그래프

 

그래프 이론중 이분 그래프에 대해 학습하기 좋은 문제를 찾아서 한번 이분 그래프에 대해 알아보고

 

해당 문제를 풀이해보겠다.

 

먼저 이분 그래프의 정의를 살펴보겠다.

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

 

모든 꼭짓점 을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

 

 

이 무슨 소리야라는 말이 절로 나올 수 있다. 

 

간단히 말해서 그래프의 모든 정점을 두가지 색으로만 표현이 가능해야 한단 소리인데

이때 인접한 정점끼리는 다른 색으로 표현되어 있어야 한단 것이다.

 

간단한 그래프 하나를 예시로 설명해 보도록 하겠다.

 

다음과 같은 웃기게 생긴 그래프가 존재한다고 가정할때 ,

 

정점 1에 대해 주황색으로 칠한다고 가정해보겠다.

 

 

이때 정점 1과 인접한 정점 2, 3은 이분 그래프의 정의에 따라 같은 색으로 칠해지면 안되기 때문에

그냥 초록색으로 두도록 하겠다.

 

이어서 각 정점 2, 3 에 인접한 정점들에 대해 주황색으로 색칠하게 된다면,

 

 

이제 모든 정점에 대해 색칠이 완료 되었다.

현재 그래프는 주황색과 초록색 두가지 색으로 표현이 가능해졌고,

인접한 정점끼리는 다른 색을 갖는 그래프가 되었다.

 

따라서 현재 그래프는 이분그래프라고 할 수 있다.

 

만약 정점 5, 6이 인접하다고 가정하면

 

 

이분 그래프가 될 수 없다.

 

각 정점과 인접한 정점끼리 다른 색으로 칠해야 하므로 사용하는 색의 수가 3개가 되고 이는 

이분 그래프의 정의에서 벗어나게 되므로 이분그래프라 할 수 없다.

 

이제 이분그래프란 무엇인가에 대해 알아봤으니

 

문제로 넘어가서 문제에 대한 분석을 하도록 하겠다.

 

각 테스트케이스마다 그래프에 대한 정보가 주어지고 (정점,간선)

테스트케이스의 그래프가 이분그래프인지 아닌지만 판별하면 되는 문제이다.

 

BFS로 접근하자면,

현재 테스트케이스 그래프에 대해 색칠하며 탐색을 진행하며 방문하지 않은 정점에 대해서는 

현재정점과 다른 색을 칠하며 방문처리후 큐에 삽입,

방문한 정점에 대해서는 현재 정점과 다른 색인지만 확인해주면 된다.

 

풀이에 대한 아이디어는 간단하니 바로 코드로 구현을 해보겠다.

 

먼저 입력에 대한 수가 매우 크므로 인접리스트로 구현을 하겠다.

그래프에 대해 저장할 인접리스트를 선언해준다.

 

	static ArrayList<Integer>[] edges;

 

다음으론 방문처리겸 색을 구분할 배열을 하나 선언해주도록 하겠다.

이때 단순히 두가지 색으로만 나뉘면 되기 때문에 boolean 타입의 wrapper 클래스인 Boolean 배열로 선언해주어

미방문인경우 null 방문인경우 true, false 두가지로 구분이 가능하도록 한다.

 

	static Boolean[] visit;

 

이제 현재 정점에 대해 저장하고 판단할 큐인데 이때 현재정점의 번호와 현재정점에 칠해진 색이 뭔지에 대해

저장하고 있어야 하므로 별도의 클래스를 하나 만들어 주도록하겠다.

 

class Node{
	boolean v;
	int no;
	Node(boolean v, int no){
		this.v = v;
		this.no = no;
	}
}

 

그리고 해당 클래스로 배열을 만들어 큐로 사용한다.

 

	static Node[] queue;

 

다음은 여러번의 테스트 케이스를 받으므로 각 테스트 케이스마다 초기화 해줄수 있는 메소드를 하나 만들어준다.

주의할것은 front ,rear 역시 초기화 해주어야 한단 점이다.

	@SuppressWarnings("unchecked")
	static void setting() { // 초기화
		front = rear = 0;
		edges = new ArrayList[n + 1];
		visit = new Boolean[n + 1];
		queue = new Node[n];
		for(int i = 1; i <= n; i++) {
			edges[i] = new ArrayList<>();
		}
	}

 

이제 인접리스트의 간선 입력시 저장시켜줄 메소드이다.

 

	static void init(int a, int b) {
		edges[a].add(b);
		edges[b].add(a);
	}

 

이제 문제 풀이의 핵심 알고리즘인 BFS를 구현하면 된다.

 

먼저 현재 그래프가 전부 연결상태인지 알 수 가 없기 때문에 반복문을 통해 방문하지 않은 모든 정점을

시작점으로 두어 탐색할수 있도록 하겠다.

 

이때 탐색이 모두 완료되었을 땐 YES를 리턴할수 있도록 해주었다.

 

	static String bfs() {
		for(int j = 1; j <= n; j++) {
			if(visit[j] == null) {
				queue[rear++] = new Node(true, j);
				visit[j] = true;
				
				
			}
		}
		
		return "YES\n";
	}

 

 

다음은 현재 정점을 꺼내 현재 정점과 인접한 정점을 순회하며

방문하지 않은 경우 즉 visit == null 인경우는 현재 정점과 다른 boolean 타입의 값으로 방문처리후 큐에 삽입 해주고

방문한 경우는 현재 정점과 방문 정점의 boolean 타입이 같은 경우 바로 NO를 리턴시켜

메소드를 종료할수 있도록 해준다.

 

	static String bfs() {
		for(int j = 1; j <= n; j++) {
			if(visit[j] == null) {
				queue[rear++] = new Node(true, j);
				visit[j] = true;
				
				while(queue[front] != null) {
					Node edge = queue[front];
					queue[front++] = null;
					front%=n;
					for(int i : edges[edge.no]) {
						if(visit[i] == null) { // 방문하지 않은 정점의 경우
							queue[rear++] = new Node(!edge.v,i);
							rear%=n;
							visit[i] = !edge.v;
						}else {
							if(visit[i] == edge.v) return "NO\n";
						}
					}
				}
			}
		}
		
		return "YES\n";
	}

 

이제 여러 반례에 대해서 정확한 답을 내는것을 확인할 수 있다.

 

1
6 6
1 3
3 4
4 2
2 5
5 6
6 1
YES

2
3 3
1 2
2 3
1 3
2 1
1 2
NO 
YES

1
5 4
1 2
2 3
3 1
4 5
NO

1
4 2
1 2
3 4
YES


1
5 4
1 2
3 4
4 5
3 5
NO

1
4 3
1 4
4 3
3 2
YES

1
5 4
1 2
1 3
2 4
3 5
YES

1
4 3
1 2
4 3
2 3
YES

 

 

아래는 코드의 전문이다.

 

package boj3;

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

public class Boj1707 {
	
	/*
	 * 제출 完
	 */
	
	static int n,front,rear;
	
	static Boolean[] visit;
	static Node[] queue;
	static ArrayList<Integer>[] edges;
	
	@SuppressWarnings("unchecked")
	static void setting() { // 초기화
		front = rear = 0;
		edges = new ArrayList[n + 1];
		visit = new Boolean[n + 1];
		queue = new Node[n];
		for(int i = 1; i <= n; i++) {
			edges[i] = new ArrayList<>();
		}
	}
	
	static void init(int a, int b) {
		edges[a].add(b);
		edges[b].add(a);
	}
	
	static String bfs() {
		for(int j = 1; j <= n; j++) {
			if(visit[j] == null) {
				queue[rear++] = new Node(true, j);
				visit[j] = true;
				
				while(queue[front] != null) {
					Node edge = queue[front];
					queue[front++] = null;
					front%=n;
					for(int i : edges[edge.no]) {
						if(visit[i] == null) { // 방문하지 않은 정점의 경우
							queue[rear++] = new Node(!edge.v,i);
							rear%=n;
							visit[i] = !edge.v;
						}else {
							if(visit[i] == edge.v) return "NO\n";
						}
					}
				}
			}
		}
		
		return "YES\n";
	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int k = Integer.parseInt(in.readLine());
		
		while(k-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			n = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			setting();
			
			while(e-- > 0) {
				st = new StringTokenizer(in.readLine()," ");
				init(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			}
			
			sb.append(bfs());
		}
		
		in.close();
		
		System.out.print(sb);
		
	}

}


class Node{
	boolean v;
	int no;
	Node(boolean v, int no){
		this.v = v;
		this.no = no;
	}
}