[백준 - 1707] 이분 그래프 .java

https://www.acmicpc.net/problem/1707

 

이분 그래프

각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때의 그래프

 

1. 각 노드에 대해, 인접한 노드가 이미 방문된 경우 그 노드가 속한 집합을 확인
2. 만약 인접한 노드가 같은 집합에 속한다면, 이는 이분 그래프가 아님을 의미
3. 왜냐하면 이분 그래프에서는 인접한 노드가 반드시 다른 집합에 속해야 하기 때문

=> 탐색한 노드에 다시 접근하게 됐을때(이미 방문한 노드), 현재 노드의 집합과 같으면 이분 그래프가 아니다.

=> 두 개의 집합으로 나눠야한다

-> 여러 부분으로 나눠진 그래프일 수 있음 => 모든 노드로 각각 DFS 탐색! 

check[now] = (check[node] + 1) % 2;

 

현재 노드 node가 속한 집합이 0이라면, 인접 노드 now는 1로 설정
현재 노드 node가 속한 집합이 1이라면, 인접 노드 now는 0으로 설정

 

 

 

else if (check[now] == check[node]) { isEven = false; }

 

인접 노드 now가 이미 방문된 경우, check[now]와 check[node]가 같다면 같은 집합에 속한다는 뜻입
이는 이분 그래프가 아님을 의미하므로, isEven을 false로 설정

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; //그래프를 저장할 인접 리스트 배열
    static int[] check; //노드의 집합 정보를 저장할 배열 (0 또는 1)
    static boolean[] visited; //방문배열
    static boolean isEven; //이분 그래프 여부

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int k = Integer.parseInt(br.readLine()); //테스트케이스 개수
        for(int i = 0; i < k; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken()); //노드 개수
            int e = Integer.parseInt(st.nextToken()); //에지 개수

            graph = new ArrayList[v+1]; //1부터 노드 시작
            visited = new boolean[v+1];
            check = new int[v+1];
            isEven =true;

            //각 노드의 인접 리스트 초기화
            for(int j = 1; j <= v; j++){
                graph[j] = new ArrayList<Integer>();
            }
            //에지 정보
            for(int j = 0; j < e; j++){
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());

                graph[start].add(end);
                graph[end].add(start);
            }

            //모든 노드에서 DFS 수행
            for(int j = 1; j <= v; j++) {
                if (isEven) DFS(j);
                //이분 그래프가 아니면 중단
                else break;
            }
            //출력
            if (isEven) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    static void DFS(int node){
        visited[node] = true; //방문처리
        for(int now : graph[node]){
            if(!visited[now]){
                //이전 노드와 다른 집합으로 설정
                check[now] = (check[node] + 1) % 2;//0,1의 집합으로
                DFS(now);
            }
            //이미 방문되었는데 이전 노드와 같은 집합에 속하면
            else if(check[now] == check[node]) {
                isEven = false; //이분그래프가 아님
            }
        }
    }


}