[백준] 1707 : 이분 그래프 JAVA 풀이

 

이분 그래프란 그래프의 정점들을 두 가지 색으로 칠할 때,

한 정점과 인접해있는 정점들이 서로 다른 색일 때를 말한다.

 

입력 예제 그래프로 예를 들어보면 이렇다.

두 번째 그래프는 2를 기준으로 3, 4가 파란색이어야 한다.

3을 기준으로는 2, 4가 빨간색이어야 한다.

4를 기준으로는 2, 3이 빨간색이어야 한다.

따라서 두 번째 그래프는 이분 그래프가 될 수 없다.

 

 

1. Node 클래스를 생성함.
    노드의 인덱스인 idx, 노드의 색깔인 color, 인접노드를 저장할 ArrayList인 child를 멤버변수로 설정

2. V개의 노드를 저장할 Node 배열을 생성함

3. V개의 노드를 방문했는지 검사할 boolean 배열을 생성함

4. 그래프에 대한 정보를 입력받고 양방향그래프를 생성함

5. 아직 방문하지 않은 노드가 있다면 그 정점을 1번색깔로 칠하고 bfs함수의 인자로 넘겨줌

    5-1. 인자로 넘어온 노드를 큐에 넣음

    5-2. 그 노드(부모노드)를 방문했다고 체크한 뒤, 인접노드들을 검사함

        5-2-1. 처음 방문하는 노드라면 다른 색으로 칠한 뒤 다시 큐에 넣음

        5-2-1. 이미 방문한 적이 있고 부모노드와 같은 색이라면 false를 리턴

 

이분 그래프의 개념이 생소하긴 했지만 이해하고나니 별로 어렵지 않은 문제였다!

 

import java.io.*;
import java.util.*;
public class Main {

	static class Node{
		int idx;
		int color;
        // 각 노드의 인접 노드들을 저장하는 어레이리스트
		ArrayList<Node> child = new ArrayList<>();
		
		Node(int idx, int color){
			this.idx = idx;
			this.color = color;
		}
	}
	
	static boolean[] visit;
	static Node[] graph;
	static boolean ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			ans = true;
			
			visit = new boolean[V+1];
			graph = new Node[V+1];
			
			for(int j=1;j<=V;j++) {
            	// V개의 노드들을 초기화함
				graph[j] = new Node(j, 0);
			}
			
			for(int j=0;j<E;j++) {
				st = new StringTokenizer(br.readLine()," ");
				
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
                // 양방향 그래프를 만들어줌
				graph[a].child.add(graph[b]);
				graph[b].child.add(graph[a]);
			}
			
			for(int j=1;j<=V;j++) {
				if(!visit[j]) {
					visit[j] = true;
                    // 1번 색으로 칠함
					graph[j].color = 1;
                    
                    // 이분그래프가 아니라면 ans를 false로 바꾸고 반복문 종료
					if(!bfs(j)) {
						ans = false;
						break;
					}
				}
			}
			System.out.println(ans?"YES":"NO");
		}
	}
	
	static boolean bfs(int v) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(graph[v]);
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			
            // node의 인접노드들에 대해 반복
			for(Node child : node.child) {
            	// 아직 방문하지 않은 노드면 node와 다른 색으로 칠하고 큐에 넣음
				if(!visit[child.idx]) {
					visit[child.idx] = true;
					child.color = 1+node.color;
					queue.add(child);
				}
				else {
                	// 이미 방문했던 노드이고 node와 같은 색이라면 false 리턴
					if(child.color==node.color) {
						return false;
					}
				}
			}
		}
		return true;
	}

}