[1707] 이분 그래프

✔ 이분 그래프

[백준 1707]

문제 분석하기

노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할해야 함

트리의 경우 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문에 항상 이분 그래프가 됨

하지만 사이클이 발생하여 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다고 판단할 수 있음

손으로 풀어보기

1. 그래프 데이터를 가중치 없는 인접 리스트로 구현
2. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행
   • DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별
   • 그래프의 모든 노드가 이어져 있지 않고, 여러 개의 부분 그래프로 이뤄진 케이스가 존재할 수 있으므로 모든 노드 DFS 실행
3. 이분 그래프 여부를 정답으로 출력
4. 사례의 개수만큼 위를 반복

슈도코드 작성하기

check(이분 그래프 체크 배열)
A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열)
N(테스트 케이스)
for(N의 개수만큼 반복하기) {
    V(노드 개수)
    E(엣지 개수)
    for(V의 개수만큼 반복하기) {
        A 인접 리스트의 각 ArrayList 초기화하기
    }
    for(E의 개수만큼 반복하기) {
        각 노드에서 DFS 실행 → 결과가 이분 그래프가 아니면 반복 종료
    }
    이분 그래프 여부를 정답으로 출력하기
}

DFS {
    visited 배열에 현재 노드 방문 기록하기
    if(현재 노드의 연결 노드 중 방문하지 않은 노드로) {
        현재 노드와 다른 집합으로 연결 노드 집합 저장하기
        DFS 실행하기 (재귀 형태)
    }
    else {
        이분 그래프가 아님
    }
}

코드 구현하기

/**
 * 1707) 이분_그래프
 */
public class D048_1707 {
    static ArrayList<Integer>[] A;
    static int[] check;
    static boolean[] visited;
    static boolean IsEven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(테스트 케이스)
        int N = Integer.parseInt(br.readLine());
        for (int t = 0; t < N; t++) {
            String[] s = br.readLine().split(" ");
            // V(노드 개수)
            int V = Integer.parseInt(s[0]);
            // E(엣지 개수)
            int E = Integer.parseInt(s[1]);
            // A(그래프 데이터 저장 인접 리스트)
            A = new ArrayList[V + 1];
            // visited(방문 기록 저장 배열)
            visited = new boolean[V + 1];
            // check(이분 그래프 체크 배열)
            check = new int[V + 1];
            IsEven = true;
            for (int i = 1; i <= V; i++) {
                // A 인접 리스트의 각 ArrayList 초기화하기
                A[i] = new ArrayList<Integer>();
            }
            for (int i = 0; i < E; i++) {
                // 인접 리스트로 그래프 저장하기
                s = br.readLine().split(" ");
                int Start = Integer.parseInt(s[0]);
                int End = Integer.parseInt(s[1]);
                A[Start].add(End);
                A[End].add(Start);
            }
            // 각 노드에서 DFS 실행 → 결과가 이분 그래프가 아니면 반복 종료
            for (int i = 1; i <= V; i++) {
                if (IsEven) {
                    DFS(i);
                } else {
                    break;
                }
            }
            // 이분 그래프 여부를 정답으로 출력하기
            if (IsEven) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    public static void DFS(int node) {
        // visited 배열에 현재 노드 방문 기록하기
        visited[node] = true;
        for (int i : A[node]) {
            // 인접한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리하기 (0, 1)
            if (!visited[i]) {
                check[i] = (check[node] + 1) % 2;
                DFS(i);
            } // 이미 방문한 노드가 현재 내 노드와 같은 집합이면 이분 그래프가 아님
            else if (check[node] == check[i]) {
                IsEven = false;
            }
        }
    }
}