728x90
문제
접근 방식
이분 그래프의 개념만 알면 BFS나 DFS로 쉽게 풀 수 있는 문제다.
위와 같은 그래프가 주어졌을 때 DFS 탐색 순서는 아래와 같다.
1 > 2 > 3 > 4 > 2 > 4
이분 그래프는 모든 정점을 두 가지 색으로만 칠할 수 있다고 생각하면 되는데
인접한 정점을 방문할 때마다 현재 정점과 반대되는 색깔로 칠하다
만약 다음에 방문할 정점이 이미 색이 칠해져있고 현재 정점과 색깔이 같다면
이분 그래프가 아니라는 것을 알 수 있다.
1번 정점 방문 => 1번 정점 빨간색으로 색칠
2번 정점 방문 => 2번 정점 파란색으로 색칠
3번 정점 방문 => 3번 정점 빨간색으로 색칠
4번 정점 방문 => 4번 정점 파란색으로 색칠
2번 정점 방문 => 2번 정점 빨간색으로 색칠 (이미 파란색인데 빨간색으로 칠할 수 없음)
== 이분 그래프가 아님
위와 같은 순서로 진행된다.
DFS로 풀었는데 인접 정점 방문하며 색칠하는거라 BFS로 푸는게 더 효율적일거 같다
풀이
public class Main {
private static int v, e, x, y;
private static ArrayList<ArrayList<Integer>> near;
private static int[] paint;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
near = new ArrayList<>();
paint = new int[v + 1];
boolean isBipartite = true;
for (int i = 0; i <= v; i++) {
near.add(new ArrayList<>());
}
while (e-- > 0) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
near.get(x).add(y);
near.get(y).add(x);
}
for (int i = 1; i <= v; i++) {
if (paint[i] != 0) continue;
if (!dfs(i, -1)) {
isBipartite = false;
break;
}
}
if (isBipartite) sb.append("YES").append("\n");
else sb.append("NO").append("\n");
}
System.out.println(sb);
}
private static boolean dfs(int cur, int prev) {
int color = -(prev);
paint[cur] = color;
for (int next : near.get(cur)) {
if (paint[next] == color) return false;
else if (paint[next] == -color) continue;
if (!dfs(next, color)) return false;
}
return true;
}
}
'Java > Algorithms' 카테고리의 다른 글
| [백준] 1043번 : 거짓말 (0) | 2024.01.27 |
|---|---|
| [백준] 2617번 : 구슬 찾기 (1) | 2024.01.26 |
| [백준] 2660번 : 회장뽑기 (0) | 2024.01.24 |
| [백준] 1260번 : DFS와 BFS (1) | 2024.01.24 |
| [백준] 11724번 : 연결 요소의 개수 (0) | 2024.01.24 |
