[백준/1707] 이분 그래프 (java)

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

1707번: 이분 그래프

---

이분 그래프 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

19214

4448

2653

22.167%

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

예제 입력 1 복사

2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2

예제 출력 1 복사

YES NO

 

---

 

- dfs를 이용하여 문제를 풀었는데, 처음에 단순하게 풀었던 인접행렬로 문제를 풀었다가

계속 틀렸다.. 1시간반 넘게 좌절하고 있다가 다른 코드를 참고해보니 인접행렬로 하게되면 메모리 초과가 떠서

인접리스트로 풀어야 풀 수 있었다.

package test1;
import java.util.*;
 
public class bj_1707_arr {
 
    public static void main(String[] args) {        
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while ( t-- > 0 ) {
            int n = sc.nextInt();
            int e = sc.nextInt();
            int[][] d = new int[n+1][n+1];
            int[] check = new int[n+1];
            boolean rt = false ;
            
            for ( int i =0 ; i < e ; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
            
                d[u][v] = v ; d[v][u] = u; 
            }
            
            for ( int i= 1 ; i <= n ; i++ ) {
                //아직 check 안한 부분 검사
                if ( check[i] == 0   ) {
                    rt = dfs(d , check , i, 1);
                }
            }
            
            System.out.println( rt==true?"YES":"NO" );
        }
        
        
    }
    
    public static boolean dfs(int[][] d, int[] c , int x, int cnt) {
        c[x] = cnt;
        
        for ( int i = 1 ; i < d[x].length ; i ++ ) {
            int next = d[x][i];
            if ( c[i] == 0 && d[x][i] == i) {
                if ( dfs( d , c , i , 3-cnt ) == false ) {
                    return false;
                }
            }
            else if ( c[next] == c[x] && d[x][i] == i ) {
                return false;
            }
        }
        
        return true;
    }
}
 

이렇게 되면 int[][] d 에 0 값이여도 모두 조회를 하기 때문에 메모리값(제한 256mb)을 초과하게 된다.

 ArrayList<Integer> 형태를 배열로 지정해두면 값이 있는것들만 저장해둘 수 있기 때문에 인접리스트로 접근합니다.

package test1;
import java.util.*;
 
public class bj_1707 {
 
    public static void main(String[] args) {
        /*
         *  2
            3 2
            1 3
            2 3
            4 4
            1 2
            2 3
            3 4
            4 2
            
            YES
            NO
         * */
        
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while ( t-- > 0 ) {
            int n = sc.nextInt();
            int e = sc.nextInt();
            //ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
            ArrayList<Integer>[] d = ( ArrayList<Integer>[] ) new ArrayList[n+1];
            int[] check = new int[n+1];
            boolean rt = false ;
            for (int i=1; i<=n; i++) {
                    d[i] = new ArrayList<Integer>();
            }
              
            for ( int i =0 ; i < e ; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
            
                d[u].add(v); d[v].add(u); 
            }
            
            for ( int i= 1 ; i <= n ; i++ ) {
                //아직 check 안한 부분 검사
                if ( check[i] == 0   ) {
                    rt = dfs(d , check , i, 1);
                }
            }
            
            for ( int i=1 ; i<=n; i++) {
                for ( int x : d[i]) {
                    if ( check[i] == check[x] ) {
                        rt= false;
                    }
                }
            }
            
            System.out.println( rt==true?"YES":"NO" );
        }
        
        
    }
    
    public static boolean dfs(ArrayList<Integer>[] d, int[] c , int x, int cnt) {
        c[x] = cnt;
        
        for ( int i : d[x] ) {
            if ( c[i] == 0 ) {
                if ( dfs( d , c , i , 3-cnt ) == false ) {
                    return false;
                }
            }
 
        }
        
        return true;
    }
}