문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
2 ≤ K ≤ 5
1 ≤ V ≤ 20,000
1 ≤ E ≤ 200,000
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
풀이
이분 그래프가 뭔지 몰라서 문제만 읽고 처음에는 서로 인접하지 않은 정점끼리 혹은 그래프를 두개로 나누라는 건가 싶었다. 좀 고민하다가 답안을 보려고 구글링을 했는데 이분 그래프에 대한 설명이 먼저 있어서 설명을 듣고 다시 풀이했다.
우선 이분 그래프는 쉽게 생각하면 어릴 적에 경우의 수에서 했던 이웃하는 면에 같은 색을 칠하지 않는다와 비슷하다.
그래프의 노드들을 빨강, 파랑으로 채울 수 있는데 인접한 노드의 색이 같은 색이 존재하지 않는다면 이분 그래프이다.
위 그림을 보면 1번 그림은 이분 그래프이지만, 2번은 이분 그래프가 아니다. 이유가 뭘까?
문제에서 이분 그래프의 정의로 이해해보자.
그래프의 정점의 집합을 둘로 분할해본다. 파랑, 빨강
각 집합에 속한 정점끼리는 인접하지 않는다.
1번 그림에서 빨강 2, 3번 노드는 인접하지 않으면서 같은 빨강 집합이다.
1번 그림에서 파랑 1, 4번 노드는 인접하지 않으면서 같은 파랑 집합이다.
반면, 2번 그림에서 2, 3번 노드는 인접하지 않지만,
1번과 4번 노드는 간선으로 연결되어 인접하고 있으므로 이분 그래프라고 볼 수 없다.
이분 그래프에 대해 알았으면 이제 문제 해결을 해보자.
그래프의 간선을 입력 받아 ArrayList[]인 graph에 연결 관계를 입력했다.
이때, 그래프는 무방향 그래프이기 때문에 입력이 A B 로 주어지면 노드 A가 연결된 노드에 B도 저장하고, 노드 B에도 A를 저장한다. 이유는 풀이를 마치고 작성하겠다.
그래프를 저장하고, 정점 수 + 1 크기의 visited[]를 만든다.
연결 관계를 확인하기 위해서 bfs를 사용하였다. dfs로도 풀 수 있으나 가끔 재귀 호출로 인한 시간 초과나 메모리 초과가 발생할 수 있어서 꼭 dfs를 활용 안해도 될 것 같을 땐 bfs로 우선 풀어보고 있다.
그래프가 연결되어 있지 않은 단절된 그래프 입력이 들어올 수도 있어서 모든 노드에 대해서 bfs를 시작해보도록 한다.
그렇지만 이미 방문했을 경우 bfs를 하지 않도록 조건을 걸어놨기 때문에 무의미한 bfs호출은 없다.
시작 노드를 매개변수로 받아서 Queue에 넣고, 시작 노드는 visited 배열에 1로 저장하고 시작한다.
시작 노드에 연결된 노드들을 하나씩 꺼내서 방문하지 않았으면 visited 배열에 시작 노드에 반대값을 visited에 저장한다.
1인 경우 -1, -1인 경우 1로.
나중에 생각든건데 굳이 내 코드처럼 조건문을 안달고, 이전값에 음수만 붙이면 더 간결해질 것 같다. 코드 수정을 하지 않은 이유는 이 방식은 다른 사람의 코드를 보고 알아차린 것이기 때문.
만약 시작 노드에 연결된 노드가 이미 방문된 노드일 경우 visited 배열에서 시작 노드와 같은 값인지를 확인한다.
같은 값이라면 인접한 노드가 같은 색상을 띈다는 의미로 이분그래프가 될 수 없음을 뜻한다.
그러므로 bpg(Bipartite Graph)를 true로 바꿔서 이분그래프가 아님을 알리고 반복을 종료한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class boj1707 {
static boolean bpg;
static int[] visited;
static ArrayList<Integer> graph[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer stk = new StringTokenizer(br.readLine());
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
graph = new ArrayList[V + 1];
for (int i = 0; i <= V; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
stk = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(stk.nextToken());
int v2 = Integer.parseInt(stk.nextToken());
graph[v1].add(v2);
graph[v2].add(v1);
}
bpg = false;
visited = new int[V+1];
for (int i = 1; i <= V; i++) {
if (visited[i] == 0)
bfs(i);
if (bpg)
break;
}
if (bpg)
System.out.println("NO");
else
System.out.println("YES");
}
}
public static void bfs(int idx) {
Queue<Integer> queue = new LinkedList<>();
queue.add(idx);
visited[idx] = 1;
while (!queue.isEmpty()) {
int val = queue.poll();
for (Integer i : graph[val]) {
if (visited[i] == 0) {
if (visited[val] == 1)
visited[i] = -1;
else if (visited[val] == -1)
visited[i] = 1;
queue.add(i);
}
else if (visited[i] == visited[val]) {
bpg = true;
return;
}
}
}
}
}무방향 그래프이므로 양방향으로 노드의 연결관계를 저장하지 않으면 안되는 예를 들면 입력이 다음과 같이 주어진 경우이다.
5 4 <- 노드 V, 간선 E
2 3
3 4
1 42번 노드에서 시작하는 경우 visted 배열은 {1:0, 2:1, 3:-1, 4:1, 5:0} <- {인덱스:값} 이 된다.
시작하는 노드의 값은 1로 주어진다 했기 때문에 2번은 1, 2번에 연결된 3은 -1, 3에 연결된 4는 1
그럼 1번에서 시작하는 노드의 경우 1번 노드는 1인데 4번 노드는 방금 2번 노드의 연결관계에서 1로 처리가 됐다.
1번과 인접한 4번이 둘다 1이 되어 이분그래프가 아니라고 판별한다.
이것이 잘못된 이유이다. 위 그래프는 이분그래프이다. 양방향으로 입력했으면 2번 노드를 시작하면서 3번 노드를 지나 4번 노드와 연결된 1번 노드가 -1로 저장됐을 것이다.
이 문제를 통해서 별다른 방향성을 띄지 않는다면 반드시 양방향으로 처리해야 한다고 생각이 든 문제였다.
문제의 난이도는 높지 않지만 이분 그래프를 몰랐다면 풀기 힘들었을 것이라 생각한다.
