성능 요약
메모리: 326684 KB, 시간: 2456 ms
분류
너비 우선 탐색, 이분 그래프, 깊이 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2024년 8월 23일 18:25:03
문제 설명
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
풀이
Java
import java.util.*;
public class Main {
static int K; // 테스트 케이스 수
static int V; // 정점의 수
static int E; // 간선의 수
static String answer;
static ArrayList<ArrayList<Integer>> graph;
static int[] set;
public static void main(String[] args) {
int p1, p2; // 두 정점; 간선
Scanner scan = new Scanner(System.in);
K = scan.nextInt();
while (K-- > 0) {
answer = "YES";
V = scan.nextInt(); // 정점
E = scan.nextInt(); // 간선
graph = new ArrayList<>();
for (int i = 0; i < V; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
p1 = scan.nextInt() - 1;
p2 = scan.nextInt() - 1;
// 양방향 간선 추가
graph.get(p1).add(p2);
graph.get(p2).add(p1);
}
set = new int[V];
for (int i = 0; i < V; i++) {
if (set[i] == 0) {
if (!bfs(i)) break;
}
}
System.out.println(answer);
}
}
// bfs
public static boolean bfs(int n) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(n);
set[n] = 1;
while (!queue.isEmpty()) {
n = queue.poll();
for (Integer i : graph.get(n)) {
if (set[n] == set[i]) {
answer = "NO";
return false;
}
if (set[i] == 0) {
set[i] = set[n] * -1;
queue.add(i);
}
}
}
return true;
}
}