728x90
1707 - 이분 그래프
https://www.acmicpc.net/problem/1707

문제
이분 그래프(Bipartite Graph)
: 그래프의 정점의 집합을 둘로 분할해 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할한 그래프
입력
첫째 줄: 테스트 케이스 개수 K
각 테스트 케이스 첫째 줄: 그래프 정점의 개수 V, 간선의 개수 E (각 정점에는 1부터 V까지 차례로 번호)
둘째 줄 ~ E개 줄: 인접한 두 정점의 번호 u, v (u != v, 간선의 대한 정보)
출력: 이분 그래프 O -> YES / X -> NO 순서대로 출력
풀이
이분 그래프
그래프의 모든 정점을 두 그룹(A, B)로 나눴을 때 인접한 두 정점이 같은 그룹 속하지 않게 나눌 수 있어야 함
= 인접한 정점은 항상 반대편 그룹이어야 함
- 시작 노드 색(1) 칠함 / BFS로 탐색하며 연결된 노드 반대 색(-1) 칠함
- `color[next] == 0`: 아직 방문 X 노드 -> 반대 색으로 칠하고 큐에 추가
- `color[next] == color[cur]`: 이미 같은 색으로 칠해진 인접 정점 => 이분 그래프 X
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
color[start] = 1;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph.get(cur)) {
if (color[next] == 0) {
color[next] = -color[cur];
queue.offer(next);
} else if (color[next] == color[cur]) {
flag = false;
return;
}
}
}
}
코드
import java.io.*;
import java.util.*;
// 이분 그래프
public class boj_1707 {
static int[] color;
static List<List<Integer>> graph;
static boolean flag;
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
color[start] = 1;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph.get(cur)) {
if (color[next] == 0) {
color[next] = -color[cur];
queue.offer(next);
} else if (color[next] == color[cur]) {
flag = false;
return;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int K = Integer.parseInt(br.readLine());
while (K-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph.get(u).add(v);
graph.get(v).add(u);
}
color = new int[V + 1];
flag = true;
for (int i = 1; i <= V; i++) {
if (color[i] == 0) bfs(i);
}
sb.append(flag ? "YES" : "NO").append("\n");
}
System.out.println(sb);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ] 백준 2166 - 다각형의 면적 (Java) (0) | 2025.11.14 |
|---|---|
| [BOJ/DP] 백준 1106 - 호텔 (Java) (0) | 2025.11.13 |
| [BOJ/DFS+BFS] 백준 14502 - 연구소 (Java) (0) | 2025.11.12 |
| [BOJ/Dijkstra] 백준 1504 - 특정한 최단 경로 (Java) (0) | 2025.11.11 |
| [BOJ/MST] 백준 1647 - 도시 분할 계획 (Java) (0) | 2025.11.11 |