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

 

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

1707번: 이분 그래프

 

난이도 : 골드 4

 

우선 이 문제를 풀기 위해서는 이분 그래프에 대해 알아야 합니다.

저는 문제를 처음 읽었을 때 이분 그래프를 잘못 이해해서 이상한 방향으로 갔습니다.

이런식으로 그래프가 2덩어리로 나눠진 것을 찾는 문제인지 알았어요..

 

 

하지만 이런 친구가 이분 그래프였습니다.

이분 그래프에 대해 쉽게 설명드리겠습니다.

전 어렵고 전문적이게 설명을 못 하기 때문이예요.

 

저는 이렇게 이해했어요. 강을 건널 때 돌 2개로 건널 수 있잖아요.

A, B 돌이 있다치면 A 놓고 건너고, B 놓고 건너고, A 놓고 건너고, B 놓고 건너고........

 

이분 그래프도 같습니다. 정점을 이동할 때 각 정점에 숫자를 부여합니다.

예를 들어 1과 2로요. 그래서 이 1과 2로 모든 그래프를 건널 수 있으면 이분 그래프예요.

그림으로 볼게요. 

 

2번 부터 출발해서 초록색이 1, 파란색이 2라고 할게요.

1, 2를 번갈아가면서 그래프를 모두 탐색했으면 이분 그래프입니다.

이분 그래프가 아닌 것은 뭘까요?

 

??? 이게 맞나요?

7번에서 5번으로 건너려는데 2번 파란색이 필요하대요. 이미 밟고 있는데.

이분 그래프가 아닙니다.

 

 

얘도 이분 그래프입니다.

눈이 아플정도로 어지럽지만 1, 2, 1, 2, ....... 이분 그래프죠?

 

즉, 이분 그래프는 어떤 한 정점에서 연결된 모든 다른 정점이 다른 값을 가져야합니다.

 

이것으로 개념을 잡았고 문제를 풀어봅시다.

개념을 잡았으면 쉽게 문제를 풀 수 있습니다.

 

저는 ArrayList[]를 활용하여 모든 정점을 연결한 값을 ArrayList[]에 저장했습니다.

입력받을 때 주의사항은 A-B를 연결했으면 B-A도 연결해야 합니다.

그래서 입력 1개를 받으면 2번 저장해야해요.

Queue를 활용한 BFS로 문제를 풀었고, 모든 정점에 대해 방문 검사를 하고 1번 2번 달아주는 식으로 풀었습니다.

각 정점에 번호를 달아줄 때 현재 정점과 연결된 정점의 숫자가 같으면 이분 그래프가 아닙니다.

---

전역 변수 

v, e = 정점과 간선의 갯수

al[] = 각 정점의 연결 정점을 저장하는 ArrayList

visit[] = 방문과 숫자를 관리(방문 전 = 0, 방문 후 = 1 or 2)

메소드

void main 

입력을 받습니다. (grouping 호출)

void grouping

1부터 v까지 모든 정점에 대해 이분 그래프 검사를 합니다.

Queue를 활용한 BFS이고, 각 정점의 연결된 모든 정점에 대해 검사를 합니다.

연결된 정점이 0이라면 1 or 2를 부여하고 현재 정점과 연결 정점의 숫자가 같다면

이분 그래프가 아닙니다. 

import java.io.*;
import java.util.*;

public class p1707 {
	static int v, e;
	static ArrayList<Integer>[] al;
	static int visit[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(stz.nextToken());

		for(int tc = 0; tc < t; tc++) {
			stz = new StringTokenizer(br.readLine());
			v = Integer.parseInt(stz.nextToken());
			e = Integer.parseInt(stz.nextToken());
			visit = new int[v+1];
			al = new ArrayList[v+1];

			for(int i = 0; i <= v; i++)
				al[i] = new ArrayList<Integer>();

			for(int i = 0; i < e; i++) {
				stz = new StringTokenizer(br.readLine());
				int p1 = Integer.parseInt(stz.nextToken());
				int p2 = Integer.parseInt(stz.nextToken());

				al[p1].add(p2);
				al[p2].add(p1);
			}
			grouping();
		}
	}

	public static void grouping() {
		Queue<Integer> q = new LinkedList<Integer>();

		for(int i = 1; i <= v; i++) {
			if(visit[i] == 0) {
				q.add(i);
				visit[i] = 1;
			}

			while(!q.isEmpty()) {
				int now = q.poll();

				for(int j = 0; j < al[now].size(); j++) {
					if(visit[al[now].get(j)] == 0) {
						q.add(al[now].get(j));
					}
					
					if(visit[al[now].get(j)] == visit[now]) {
						System.out.println("NO");
						return;
					}

					if(visit[now] == 1 && visit[al[now].get(j)] == 0)
						visit[al[now].get(j)] = 2;
					else if(visit[now] == 2 && visit[al[now].get(j)] == 0)
						visit[al[now].get(j)] = 1;
				}
			}
		}

		System.out.println("YES");
	}

}

이분 그래프 개념만 알고 있다면 어렵지 않게 풀 수 있는 문제였습니다.