이분 그래프는 요약해서 말하자며 어떤 한 정점에서 연결된 모든 정점이 다른 값을 가져야 한다는 의미이다.
더 자세한 내용은 풀이에서 이어서 설명하겠다.
-
📚 Process
초기화 및 선언
: 테스트 케이스 T와 정점의 개수 V, 간선 E 를 입력받고 차례대로 넣어준다. 필자는 그래프의 연결관계에 ArrayList 를 사용하였다. 이런 그래프 간의 문제는 ArrayList 의 사용이 편한 것 같다.
이어서 V+1 만큼 생성해주고 각각 ArrayList 를 만들어준다.
그리고 양방향 으로 표현해 주었다. 이는 연결된 모든 정점간의 값을 확인해주기 위해서이다.
또한 방문 여부를 확인하기 위해 boolean[] visit도 사용하겠다.
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static Scanner sc = new Scanner(System.in);
static int T, V, E;
static ArrayList<Integer>[] adj;
static int[] visit;
public static void main(String[] args) throws IOException {
T = sc.nextInt();
while(T-- >0) {
input();
pro();
}
}
public static void input() throws IOException {
V = sc.nextInt();
E = sc.nextInt();
adj = new ArrayList[V+1];
visit = new int[V+1];
for(int i=1; i<=V; i++) adj[i] = new ArrayList<>();
while(E-- >0) {
int x = sc.nextInt();
int y = sc.nextInt();
adj[x].add(y);
adj[y].add(x);
}
}
BFS(탐색)
: 이번 풀이에서 visit은 정점의 값을 의미한다. 0은 방문하지 않은 정점, 1,2는 서로 다른 정점을 표기한다.
BFS 풀이의 기본인 Queue 를 사용한다. 모든 정점을 탐색하며 방문하지 않은 연결된 정점이 있다면 값을 1로 선언해주고 큐에 삽입한다. 그 후, 큐에 들어간 정점과 연결된 모든 정점을 확인한다. 여기서 설명하기 쉽게 현재 정점은 nowDot, 연결된 정점은 connectedDot 으로 설명하겠다.
1. nowDot 의 값과 connectedDot의 값이 같으면 즉, 이분 그래프가 아니기 때문에 "NO" 를 반환한다.
2. connectedDot이 방문한 적이 없다면
2-1. 큐에 삽임
2-2. nowDot과 다른 값을 부여
위의 단계를 거쳐 모든 탐색을 마친다. 정상적으로 탐색이 마쳐진다면 "YES"를 출력하고 그게 아니라면 중간에 "NO"를 반환할 것이다.
✅ 전체 코드
: 이분 그래프의 의미에 대해 깊게 생각해 볼 수 있는 좋은 문제였다. 이러한 그래프 이론 문제를 DFS & BFS 모두를 이용하여 풀이하는 습관을 들여야겠다 ..
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static Scanner sc = new Scanner(System.in);
static int T, V, E;
static ArrayList<Integer>[] adj;
static int[] visit;
public static void main(String[] args) throws IOException {
T = sc.nextInt();
while(T-- >0) {
input();
pro();
}
}
public static void input() throws IOException {
V = sc.nextInt();
E = sc.nextInt();
adj = new ArrayList[V+1];
visit = new int[V+1];
for(int i=1; i<=V; i++) adj[i] = new ArrayList<>();
while(E-- >0) {
int x = sc.nextInt();
int y = sc.nextInt();
adj[x].add(y);
adj[y].add(x);
}
}
/*
* 이분 그래프는 어떤 한 정점에서 연결된 모든 다른 정점이 다른 값을 가져야합니다.
* int[] visit 으로 표현하자면
* 0 : 방문하지 않음
* 1,2 : 서로 다른 정점을 표기
*/
public static void pro() {
Queue<Integer> q = new LinkedList<>();
// 모든 정점을 탐색
for(int i=1; i<=V; i++) {
// 해당 정점을 방문한 적이 없다면 큐에 INSERT
if(visit[i] == 0) {
q.add(i);
visit[i] = 1;
}
while(!q.isEmpty()) {
int now = q.poll();
// 해당 정점과 연결된 모든 정점탐색 시작
for(int j=0; j<adj[now].size(); j++) {
int connectedDot = adj[now].get(j);
// 현재 정점과 연결된 정점의 색이 같다면 이분 그래프가 아님!
if(visit[connectedDot] == visit[now]) {
System.out.println("NO");
return;
}
// 연결된 정점이 방문한 적이 없다면
if(visit[connectedDot] == 0) {
// 큐에 넣어서 탐색
q.add(connectedDot);
// 현재 정점과 다른 색상을 부여,
// visit[now] 는 색상을 부여받고 큐에 넣어지기 때문에 0인 가능성을 배제
visit[connectedDot] = (visit[now] == 1) ? 2 : 1;
}
}
}
}
System.out.println("YES");
}
}