[BOJ] 1707. 이분 그래프

그래프를 구현하는 문제였다.

그래프를 구현하기 위해 메모리측면을 고려하여 배열보단 리스트를 사용하였다. 리스트로 그래프를 구성한 후 재귀를 이용한 DFS를 이용하여 모든 정점을 방문하도록 하였다. 방문하는 과정에서 flag를 인자로 주어 두팀으로 나눌 수있도록하였다. 모든 DFS끝난 후 바로 이어서 다시 방문하여서 만일 같은 flag를 가지고 있다면 조건을 만족하지 않는 식으로 구성하였다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main_bj_1707_이분그래프 {
    static int V,E;    //정점 접선
    static ArrayList<Integer>[] graph;
    static boolean[] visit;
    static boolean[] left;
    static Stack<Integer> stack;
    
    static boolean result;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T= Integer.parseInt(br.readLine());
        for(int tc=1;tc<=T;tc++) {
            st= new StringTokenizer(br.readLine());
            V=Integer.parseInt(st.nextToken());        //간선
            E=Integer.parseInt(st.nextToken());        //정점
            
            graph=new ArrayList[V+1];    
            
            for(int i=0;i<V+1;i++) {
                graph[i]=new ArrayList<Integer>();
            }
            
            for(int i=0;i<E;i++) {
                st=new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                
                //연결 과정
                graph[u].add(v);
                graph[v].add(u);
            }
            
//            for(int i=1;i<=V;i++) {
//                System.out.println(i +" : "+graph[i]);
//            }
            
            left=new boolean[V+1];        //
            visit=new boolean[V+1];        //방문여부 확인배열
            
            result=true;
            for(int i=1;i<=V;i++) {
                if(visit[i]==false)
                    dfs(i,false);        //flag가 false이면 left, true이면 right
            }
            
            if(result)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    
    static void dfs(int node, boolean flag) {
        visit[node]=true;
        left[node]=flag;
        
//        System.out.print(node+" ");
        
        for(int next:graph[node]) {
            if(visit[next]==false) {
                dfs(next,!flag);
            }
            if(flag==left[next]) {
                result=false;
                return;
            }
            
        }
    }
}