[Java/백준/BFS, DFS] 1707번: 이분 그래프

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과 2)로 표시하는 것이다.

 

1) ArrayList 배열 adjacent을 이용해 정점간 인접관계를 표시한다.

2) BFS를 이용해서(DFS로 해도 됨) 현재 노드에서 다음 노드로 넘어갈 때 서로 다른 색을 칠한다.

2-1) 노드에 따른 색을 칠하는 것은 int 배열인 mark에 표시한다.

2-2) 이 때 이미 색이 칠해져 있다면(0이 아니라면) 현재 노드와 다음 노드가 같은 색이면 안된다.

 

주의할 점) 모든 정점이 서로 연결이 안되어 있을 수도 있다.

 

백준에서 발견한 반례 : NO가 나와야 한다.

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

 

따라서 이 부분은 main 함수에서 bfs를 호출할 때,

모든 정점을 for문으로 돌면서 색이 칠해져 있지 않은지(mark[i]==0)를 확인했다.

이 때 하나라도 bfs의 결과가 false이면 답은 NO가 된다.

 

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

public class Main {
	static int V, mark[];
	static ArrayList<Integer>[] adjacent;
	
	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());
			mark = new int[V+1];
			adjacent = new ArrayList[V+1];
			
			for(int i=0; i<=V; i++) {
				adjacent[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());
				
				adjacent[v1].add(v2);
				adjacent[v2].add(v1);
				
			}
			
			boolean flag = true;
			for(int i=1; i<=V; i++) {
				if(mark[i]==0 && !bfs(i)) {
					flag = false;
					break;
				}
			}
						
			System.out.println(flag ? "YES" : "NO");
		}
		
		br.close();
	}

	private static boolean bfs(int start) {
		
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		mark[start] = 1;
		
		while(!q.isEmpty()) {
			int node = q.poll();
			for(int e: adjacent[node]) {
				if(mark[e] == 0) {
					mark[e] = mark[node] == 1 ? 2 : 1;
					q.add(e);
				} else {
					if(mark[e] == mark[node])
						return false;
				}
			}
		}
		
		return true;
	}

}