백준 1707번 : 이분 그래프
이번 문제는 이분 그래프를 찾내는 문제이다.
여기서 이분 그래프라는 것은 그래프의 점점들을 두 개의 그룹으로 나눌 수 있고, 각 간선이 반드시 서로 다른 그룹에 속한 두 정점을 연결하는 그래프를 말한다.
다시 말해 두 그룹으로 나뉜 정점들이 자신이 속한 그룹 내의 정점과 간선으로 연결되어 있다면 이분 그래프가 아닌 것이다.
보통 이 이분 그래프를 설명할 때 파악하기 쉽게 정점에 색을 입혀 설명하는데, 나는 오히려 그게 이해가 잘 안 갔다.
또한 아래와 같이 참고한 자료들이 있는데,
이 분들이 이상하게 작성했다기 보다 내가 처음 접해보았고, 부족해서 색으로 설명을 들으니 헷갈렸다.
마지막 4번 블로그의 글을 보고 알게된 것이 위의 내용이다.
문제에서 제시되는 입력 값은 아래와 같다.
1
2
3
4
5
6
7
8
9
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
위와 같은 테스트 케이스가 주어질 때,
가장 처음 줄은 테스트 케이스의 개수, 그 다음 줄은 정점의 수 v와 간선의 수 e 이다.
그 다음으로 이어지는 입력 값은 간선의 수를 나타낸다.
현재의 경우
1
2
3
3 2
1 3
2 3
과
1
2
3
4
5
4 4
1 2
2 3
3 4
4 2
의 두 가지 테스트 케이스가 입력된 것이다.
이 문제를 풀기 위해서 먼저 인접 리스트를 구현했다.
정점, 간선 문제는 인접 리스트를 구현하여 푸는 편이 편하고 빠르다.
해당 내용은 백준 2644번 : 촌수계산 문제 정리에 나와 있으니 참고하면 좋을 것이다.
인접 리스트 구현은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
while (T-- > 0) {
st = new StringTokenizer(br.readLine());
int v = Integer.parseInt(st.nextToken()); // 정점의 개수
int e = Integer.parseInt(st.nextToken()); // 간선의 개수
tree = new ArrayList[v + 1];
color = new int[v + 1];
for (int i = 0; i <= v; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
테스트 케이스 횟수만큼 인접 리스트를 구현하고, 이분 그래프인지 아닌지를 파악해야하므로, 가장 처음 while 문으로 감쌌다.
그 다음으로는 정점의 개수 v와 간선의 개수 e를 입력 받고 해당 값을 바탕으로
1
2
3
4
5
6
7
8
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
인접 리스트를 구현했다.
앞서서 tree와 color가 나오는데, 여기서 tree는 ArrayList 형 배열로써 배열의 각 인덱스를 ArrayList로 초기화하여 인접 리스트를 표현하기 위해 사용될 자료구조이다.
이에 대한 내용도 마찬가지로 백준 2644번 : 촌수계산에 작성되어 있다.
color의 경우는 참고했던 글들에서 볼 수 있듯이 각 정점을 색으로 그룹을 구분하기 위해 사용된 정수형 배열이다.
예를 들면, 이 “색”을 바탕으로 시작 정점을 1, 시작 정점과 이어진 정점을 2라는 색으로 표현하여 그룹을 나누는 것이다.
초기 정점으로 그룹을 나누어 진행하고, 이후 같은 그룹에 같은 색이 입혀졌다면 false를 리턴하여 NO를 출력하면 된다.
해당 로직은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
boolean isBipartite = true;
for(int i=1; i <= v; i++) {
if(color[i] == 0) {
if(bfs(i)) {
isBipartite = false;
break;
}
}
}
System.out.println(isBipartite ? "YES" : "NO");
Bipartite(이분 그래프)인지를 표시하기 위한 플래그 변수를 선언하고
1부터 시작하는 정점을 v까지 반복하여 탐색한다.
만약 해당 정점의 색이 0이라면 색이 칠해지지 않은 것이고
해당 정점을 시작으로 bfs 탐색을 시작한다.
1. BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static boolean bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
color[start] = 1;
while (!q.isEmpty()) {
int node = q.poll();
for (int i : tree[node]) {
if (color[i] == 0) {
color[i] = 3 - color[node];
q.offer(i);
} else if (color[i] == color[node]) {
return true;
}
}
}
return false;
}
가장 먼저 시작 정점을 q에 삽입하고 1로 칠한다.
그 다음 큐가 빌 때까지 다음을 반복한다.
- 큐에서 정점을 꺼낸다.
- 꺼낸 정점에 인접한 모든 정점에 대해 다음을 수행한다.
- 인접한 정점이 아직 색칠되지 않았다면(color[i] == 0), 현재 정점과 다른 색을 칠하고(color[i] = 3 - color[node]), 인접한 정점을 큐에 넣는다.
- 인접한 정점이 이미 색칠되어 있고, 색이 같다면(color[i] == color[node]), 이 그래프는 이분 그래프가 아니다. 따라서 true를 반환한다.
- 모든 정점을 확인한 뒤, 큐가 비어있다면 이 그래프는 이분 그래프이다. 따라서 false를 반환한다.
- 각 정점에 대해 BFS를 수행한 후, 만약 bfs(i)가 true를 반환했다면, 이 그래프는 이분 그래프가 아니기 때문에 isBipartite 변수를 false로 초기화하고 반복을 중단한다.
이 과정을 거쳐 이분 그래프인지를 파악하려 YES or NO를 리턴한다.
DFS 탐색은 다음과 같다.
2. DFS
1
2
3
4
5
6
7
8
9
10
11
12
static boolean dfs(int node, int c) {
color[node] = c;
for (int i : tree[node]) {
if (color[i] == 0) {
if (dfs(i, 3 - c)) return true;
} else if (color[i] == color[node]) {
return true;
}
}
return false;
}
탐색에 대한 방법의 차이가 있을 뿐 색을 칠하는 방식은 동일하다.
전체 소스코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] tree;
static int[] color;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
while (T-- > 0) {
st = new StringTokenizer(br.readLine());
int v = Integer.parseInt(st.nextToken()); // 정점의 개수
int e = Integer.parseInt(st.nextToken()); // 간선의 개수
tree = new ArrayList[v + 1];
color = new int[v + 1];
for (int i = 0; i <= v; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
boolean isBipartite = true;
for(int i=1; i <= v; i++) {
if(color[i] == 0) {
if(bfs(i)) {
isBipartite = false;
break;
}
}
}
System.out.println(isBipartite ? "YES" : "NO");
}
}
static boolean bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
color[start] = 1;
while (!q.isEmpty()) {
int node = q.poll();
for (int i : tree[node]) {
if (color[i] == 0) {
color[i] = 3 - color[node];
q.offer(i);
} else if (color[i] == color[node]) {
return true;
}
}
}
return false;
}
static boolean dfs(int node, int c) {
color[node] = c;
for (int i : tree[node]) {
if (color[i] == 0) {
if (dfs(i, 3 - c)) return true;
} else if (color[i] == color[node]) {
return true;
}
}
return false;
}
}
위에서 아래로 BFS / DFS 탐색 결과이다.
“색을 칠한다.”라는 것이 헷갈릴 수 있다.
이 부분에 대한 로직 + 이분 그래프가 무엇인지에 대한 개념 두 가지 때문에 난이도가 높게 설정되어 있던거 같다.
나 역시도 이분 그래프가 무엇인지 파악하는 데에만 꽤 시간이 걸렸고, 색이라는 것에 대한 표현을 어떻게 해주어야할지도 고민했다.
어려운 문제인 만큼 기억하기 위해 기록한다.