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

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

풀이

 

1) 간선의 정보를 담을 리스트 배열 list[], 정점이 속한 팀을 나타낼 배열 team[] 을 생성한다.

2) 리스트에 양방향으로 간선의 정보를 담는다.

3) Node 클래스를 만든다. 멤버는 정점의 번호와 팀.

4) i = 1부터 V까지 team[]이 0이라면 bfs를 돌릴것이다. (0 : 아직 팀이 정해져 있지 않은 점)

• team[i] 를 1로 설정한 후 큐에 담는다 (queue.offer(new Node (i,1)))
• 큐가 빌 때까지 하나씩 빼면서 기존 정점에서 갈수 있는 다음 정점의 team이 0이라면 기존 정점의 team * -1 이다.
• 만약 다음 정점의 team이 기존 정점의 team과 같다면 이 그래프는 이분 그래프가 아니다. flag = true

5) bfs가 끝나고 flag가 true 이면 NO, false 이면 YES 를 출력한다.

 

주의사항

 

1) 모든 정점이 연결되어 있지 않을 수 있다.

즉, bfs(1) 만 해서는 이분그래프인지 확인할 수 없다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G4_1707_이분그래프 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static StringTokenizer tokens;
	static int T,V,E, team[];
	static boolean flag;
	static List<Integer> list[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for(int t=0; t<T; t++) {
			tokens = new StringTokenizer(input.readLine());
			V = Integer.parseInt(tokens.nextToken());
			E = Integer.parseInt(tokens.nextToken());
			team = new int[V+1];
			list = new List[V+1];
			for(int i=1; i<V+1; i++) {
				list[i] = new ArrayList<>();
			}
			
			for(int e=0; e<E; e++) {
				tokens = new StringTokenizer(input.readLine());
				int start = Integer.parseInt(tokens.nextToken());
				int end = Integer.parseInt(tokens.nextToken());
				list[start].add(end);
				list[end].add(start);
			}
			flag = false;
			for(int i=1; i<=V; i++) {
				if(team[i] == 0) {
					bfs(i);
				}
			}
			if(flag) {
				output.append("NO\n");
			}else {
				output.append("YES\n");
			}
		}
		output.close();
	}

	private static void bfs(int index) throws IOException {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(index, 1));
		team[index] = 1;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			List<Integer> childs = list[front.num];
			for(int i=0; i<childs.size(); i++) {
				Integer child = childs.get(i);
				if(team[child] == 0) { // 아직 팀이 안정해져 있다?
					team[child] = front.team * -1; // front의 반대팀
					queue.offer(new Node(child, front.team*-1));
				}else { // 팀이 정해져 있다?
					if(team[child] != front.team*-1) { // front의 반대팀이 아니면 이분그래프가 아니다
						flag = true;
						return;
					}
				}
			}
		}
	}
	
	static class Node{
		int num;
		int team;
		public Node(int num, int team) {
			super();
			this.num = num;
			this.team = team;
		}
	}

	static String src =
			"2\r\n" + 
			"3 2\r\n" + 
			"1 3\r\n" + 
			"2 3\r\n" + 
			"4 4\r\n" + 
			"1 2\r\n" + 
			"2 3\r\n" + 
			"3 4\r\n" + 
			"4 2";
}

 

 

후기

 

국어 실력이 부족한지 문제의 설명을 읽고 뭘 하는것인지 정확하게 알지 못했다.

결국 솔루션에서 문제가 말하는게 무엇인지 본 후에서야 코드를 작성할 수 있었다.

그래도 말만 이해하면 풀이 자체는 어렵지 않았다.

다만 이분그래프에 대한 설명이 조금 부족하다고 느꼈다.