JAVA)1707번 이분 그래프 - DFS

그래프의 정점의 집합을 둘로 분할하여,

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때,

그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

dfs로 정점들을 탐색하며 간선으로 연결된 정점들은 다른 집합에 속하도록 한다.

check[x] == 1 또는 2 // 집합 1 또는 2에 넣기 (0이면 방문 안한 정점)

 

입력 예제는 성공했지만 계속 4초에서 3초로 넘어가는 중에 실패처리가 나와서 의문이였는데

그래프가 2개 이상의 연결요소로 구성된 경우를 처리하지 않았기 때문이라는 것을 깨달았다.

(그래프의 모든 정점들이 연결되어 있지 않고 섬처럼 떨어져 있을 수도 있다는 것)

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접리스트로 그래프 구현
    static int[] check; // 각 정점의 방문여부와 소속 집합을 기록 (0:방문안함, 1:집합1, 2:집합2)

    static void dfs(int x, int prevGroup) {
        if (prevGroup == 1) check[x] = 2;
        else if (prevGroup == 2) check[x] = 1;
        for (int y : graph[x]) {
            if (check[y] == 0) { // 방문 안한 정점이면
                dfs(y, check[x]);
            }
        }
    }

    static String checkBipartite(int vertex) {
        for (int i=1;i<=vertex;i++) { // 모든 정점과 연결된 정점들에 대해 확인
            for (int x : graph[i]) { // (모든 간선을 확인)
                if (check[i] == check[x]) { // 간선으로 연결된 간선이 같은 집합에 속하면
                    return "NO"; // 이분 그래프가 아님
                }
            }
        }
        return "YES"; // 위 루프를 모두 통과하면 이분 그래프가 맞음
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt(); // 테스트 케이스 개수
        for (int i=0;i<cases;i++) {
            int n = sc.nextInt(); // 정점의 개수
            int m = sc.nextInt(); // 간선의 개수
            graph = (ArrayList<Integer>[]) new ArrayList[n+1]; // 정점의 개수만큼 리스트를 원소로 갖는 배열 생성
            for (int j=1;j<=n;j++){
                graph[j] = new ArrayList<Integer>(); // 각 정점마다 리스트 생성
            }
            for (int j=0;j<m;j++) { // 간선 저장
                int u = sc.nextInt();
                int v = sc.nextInt();
                graph[u].add(v);
                graph[v].add(u);
            }
            check = new int[n+1]; // 각 정점에 대한 방문 여부와 집합 기록 배열 생성
            // 그래프를 구성하는 연결요소가 2개 이상일 수도 있기 때문에
            // dfs 수행하고도 방문하지 않은 정점이 있는지 확인해야 함
            for (int j=1; j<=n; j++) {
                if (check[j] == 0) {
                    dfs(j, 1);
                }
            }
            System.out.println(checkBipartite(n));
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1707