이분 그래프가 뭐지..?
문제에선 일단, 그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할 할 수 있을때.. 뭐시기 저시기
이게 무슨 말이야?
그냥 그림 하나로 보면 끝.
문제에서 설명하는 방식으론 정확히 이해 되지 않았는데 해당 그림을 보고 바로 이해가 갔다.
파란 정점들끼리는 간선이 존재하지 않는다.
빨간 정점들끼리는 간선이 존재하지 않는다.
파란 정점에서 간선 하나를 타서 다른 정점으로 도착 한 경우 👉 빨간색
빨간 정점에서 간선 하나를 타서 다른 정점으로 도착 한 경우 👉 파란색
즉, 이분그래프는 간선 하나로 공유하는 인접한 정점끼리는 필수로 색(집합)이 달라야 한다.
그렇게 해야, 같은 색(집합)을 가진 정점끼리 인접하는 경우가 없다. ( 분할 가능 )
그래프의 정점의 집합을 둘로 분할 했을때 각 집합에 속한 정점끼리는 간선이 존재 하지 않는경우
그것이 이분그래프다
내가 착오한 것은
내가 착오한 것은 바로, 비연결 그래프 상황 이었다.
정점 1,2,3,4 연결이 돼있고 정점 5,6이 연결 돼 있는 분리된 비연결 그래프가 있다고 생각해보자
나는 정점1,2,3,4에서 이분그래프가 되지 않는다는 결과를 얻었어도 정점 5,6이 있기때문에 이분 그래프 즉 두가지 그래프로 분리 되는거아닌가?
같은 말도 안되는 논리에 빠졌다..
이분그래프의 정의는 그것이 아니라는걸 깨달았음
그래서 코드에다가 cnt 의 횟수를 두번 세아려서 이 경우에도 이분 그래프인 것을 처리했는데 사실 이건 필요 없는 거였다
그냥 DFS를 모든 정점마다 호출 하게끔 for문을 돌리면 비연결 그래프이지만, 이분그래프가 아닌 것 이분 그래프인것을 구할 수 있음..
📢📢비연결 그래프인데 DFS하나 달랑 놓고 완전 탐색을 바라는 순간 딜레마에 빠지게 되는 것이다
근데 문제에 비연결 그래프라고 말은 안해놓음 물론 아니라곤 말도 안함
그럼 어떻게 코드를..?
생각해보자 어처피 두가지 집합이 존재한다.
배열 하나를 만들고 그래프를 순회하면서 1,-1 로 갱신해준다.
인접 정점으로 이동 하는 경우, 출발 정점과 도착 정점의 집합은 서로 달라야만 한다.
이분 그래프를 찾기 위해서 인접하는 정점끼리는 순회하면서 다른 집합으로 갱신 해주는게 중요
union = new int[V+1]; // 각 노드가 어떤 집합인지 표시하는 배열 Union
(...)
DFS(출발 정점, 인접리스트 , 방문배열, union, sign*-1);DFS 탐색을 이용해서 모든 정점을 탐색하면서 집합을 정해준다.
재귀로 DFS를 호출할때마다 sign*-1 을 통해 집합을 두가지로 나누는 방식
그렇게 재귀를 돌다가 보면 방문한 노드를 또 방문하는 경우가 생긴다.
안생기면 애시당초 이분그래프가 맞지만, 생긴다면 확인 해줘야한다.
이미 방문한 노드에 도달했을때 해당 노드와 내 집합이 같은지 union 원소와 sign비교 후, 같은 sign이다 그렇다면 static int flag = 1
코드
import java.io.*;
import java.util.*;
public class B_1707 {
static int flag; //이분 그래프인지 판별하는 flag
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//테스트 케이스 횟수
int K = Integer.parseInt(br.readLine());
//그래프 정의
ArrayList<Integer>[] adj;
boolean[] visited;
int[] union;
for (int i = 0; i < K; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken()); //정점 수
//인접리스트 활성화
adj = new ArrayList[V+1];
for(int v=1; v<=V; v++)
adj[v] = new ArrayList<Integer>();
visited = new boolean[V+1];
union = new int[V+1];
int E = Integer.parseInt(st.nextToken()); //간선 수
for(int j=0; j<E; j++){
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
//무방향 그래프
adj[u].add(v);
adj[v].add(u);
}
//이분 그래프 테스트 시작
flag = 0;
//비연결 그래프일수도 있으니, 모든 노드에서 DFS 실행
for(int v=1; v<=V; v++){
if(!visited[v]){
DFS(v, adj, visited, union, 1);
}
}
if (flag == 1)
bw.write("NO\n");
else
bw.write("YES\n");
}
bw.flush();
bw.close();
}
static void DFS(int now, ArrayList<Integer>[] adj, boolean[] visited, int[] union, int sign){
//방문 한 노드면 종료
if(visited[now]){
if(union[now] == sign*-1)
flag = 1;
return;
}
visited[now] = true;
union[now] = sign;
for(int i=0; i<adj[now].size(); i++){
DFS(adj[now].get(i), adj, visited, union, sign*-1);
}
}
}
