백준 1707번 자바

1. 문제

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

1707번: 이분 그래프

2. 접근방식

트리 형태의 그래프인 경우 항상 이분 그래프가 된다. -> 이게 핵심이다.

즉 트리 형태가 아닌 그래프, 다시 말해서 순환형태의 그래프인 경우 이분그래프가 아니게 된다.

 

예를 들어 1 -> 2-> 3-> 1 형태의 그래프인 경우

1이 속한 집합이 A라고 가정할 때

2는 B -> 3은 A -> 1은 A가 되고 1과 3의 집합이 같기 때문에 이분그래프가 될 수 없다.

 

3. 구현

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

public class Main {

	static int K,V,E;
	static List<Integer>[] nodes;
	static boolean[] visited;
	static boolean[] checkBinary;
	static boolean isBinary;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		for (int i=0; i<K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			visited = new boolean[V+1];
			checkBinary = new boolean[V+1];
			nodes = new ArrayList[V+1];
			isBinary = true;
			
			for (int j=1; j<=V; j++) {
				nodes[j] = new ArrayList<Integer>();
			}
			for (int j=0; j<E; j++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				nodes[start].add(end);
				nodes[end].add(start);
			}

			for (int j=1; j<=V; j++) {
				if (!visited[j]) {
					dfs(j);					
				} else if (!isBinary) {
                    break;
                }
			}
			if (isBinary) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
	
	public static void dfs(int node) {
		visited[node] = true;
		for (int next : nodes[node]) {
			if (!visited[next]) {
				checkBinary[next] = !checkBinary[node];
				dfs(next);
			} else {
				if (checkBinary[node] == checkBinary[next]) {
					isBinary = false;
				}
			}
		}
	}
}

 

4. 정리

핵심을 알고보면 어렵지 않은 문제인데 핵심을 깨닫기까지가 참 오래 걸렸던 문제다.