각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때 이 그래프를 '이분 그래프(bipartite graph)'라고 한다. 그래프가 입력으로 주어졌을 때 이 그래프가 이분 그래프인지 여부를 판별하는 프로그램을 작성하시오.
(시간 제한 2초)
입력
입력은 여러 개의 사례로 구성돼 있는데, 1번째 줄에 테스트 케이스의 개수 K(2 ≤ K ≤ 5)가 주어진다.
각 사례의 1번째 줄에 그래프의 노드의 개수 V(1 ≤ V ≤ 20,000)와 에지의 개수 E(1 ≤ E ≤200,000)가 빈칸을 사이에 두고 순서대로 주어진다. 각 노드에는 1부터 V까지 차례대로 번호가 붙어 있다.
이어서 2번째 줄부터 E개의 줄에 걸쳐 에지와 관련된 정보가 주어지는데, 각 줄에 인접한 두 노드의 번호가 공백 문자를 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프면 YES, 아니면 NO를 순서대로 출력한다.
예제 입력
2 // 테스트 케이스 개수
3 2 // 노드 개수, 에지 개수
1 3
2 3
4 4 // 노드 개수, 에지 개수
1 2
2 3
3 4
4 2
예제 출력
YES
NO
1단계 - 문제 분석하기
노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할할 수 있다고 한다. 트리의 경우 탐색을 하며 다음 노드를 이번 노드와 다른 집합으로 지정하는 것으로 이분 그래프를 만들 수 있다.
단, 사이클이 발생했을 때는 이분 그래프가 불가능하다.
1번 노드를 1번 집합, 2번 노드를 2번 집합으로 설정했을 때, 3번 노드가 어떤 집합에 들어가도 항상 인접하는 노드와 같은 집합이 되어버린다.
즉, 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됬을 때 현재 노드와 집합이 같으면 이분 그래프가 불가능하다는 것으로 판별할 수 있다.
2단계 - 손으로 풀어 보기
1 입력된 그래프 데이터를 인접 리스트로 구현한다.
2 모든 노드를 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS 탐색을 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다.
3 이분 그래프 여부를 정답으로 출력한다.
현재 노드(4)와 도착 노드(2)의 집합이 같으므로 이분 그래프가 불가능 -> NO 출력
3단계 - sudo코드 작성하기
N(테스트 케이스 개수)
Check(이분 그래프 체크 배열)
A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열)
for(N의 개수만큼 반복)
{
V(노드 개수)
E(에지 개수)
for(V의 개수만큼 반복)
{
A 인접 리스트의 각 ArrayList 초기화
}
for(E의 개수만큼 반복)
{
A 인접 리스트에 그래프 데이터 저장
}
for(V의 개수만큼 반복)
{
각 노드에서 DFS 실행
-> 결과가 이분 그래프가 아니라면 반복 종료
}
이분 그래프 여부를 정답으로 출력
}
DFS
{
visited 배열에 현재 노드 방문 기록
if(현재 노드의 연결 노드 중 방문하지 않는 노드라면)
{
현재 노드와 다른 집합으로 연결 노드 집합 저장하기
DFS 실행
}
else if(이미 방문한 노드면서, 현재 노드와 같은 집합이면)
{
이분 그래프가 아님
}
}4단계 - 코드 구현하기
import java.util.ArrayList;
import java.util.Scanner;
public class Q48 {
static ArrayList<Integer>[] A;
static int[] check;
static boolean[] visited;
static boolean IsEven;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i = 0; i < N; i++){
int V = sc.nextInt();
int E = sc.nextInt();
A = new ArrayList[V + 1];
visited = new boolean[V + 1];
check = new int[V + 1];
IsEven = true;
for(int j = 1; j <= V; j++)
A[j] = new ArrayList<Integer>();
for(int j = 0; j < E; j++){
int Start = sc.nextInt();
int End = sc.nextInt();
A[Start].add(End);
A[End].add(Start);
}
for(int j = 1; j <= V; j++){
if(IsEven) {
visited = new boolean[V + 1];
check = new int[V + 1];
DFS(j);
}
else
break;
}
if(IsEven)
System.out.println("YES");
else
System.out.println("NO");
}
}
public static void DFS(int Node){
visited[Node] = true;
for(int i : A[Node]){
if(!visited[i]){
check[i] = (check[Node] + 1) % 2;
DFS(i);
}
else if(check[Node] == check[i]){
IsEven = false;
}
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
