1707. 이분 그래프

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

1707번: 이분 그래프

 

그래프가 주어졌을 때 이분 그래프인지 아닌지 판별하는 문제.

 

일단 이분 그래프는 모든 정점들이 2개의 그룹으로 나뉘어 있고, 

같은 그룹에 속해있는 정점끼리 이어져 있는 간선이 없는 그래프라고 한다. 

 

그렇다면 모든 간선의 양 정점이 서로 다른 그룹에 속해있다는 것이다. 

DFS탐색을 하면 정점에서 간선으로 이어진 다음 정점으로 계속해서 이동한다.

그렇다면 탐색을 하면서 방문 여부를 기록하는 것뿐만 아니라 

정점을 이동하면서 정점마다 0,1,0,1... 이런 식으로 다른 숫자로 기록해 놓은 후,

인접 정점이 같은 숫자로 기록돼 있다면? 이분 그래프가 아니라고 할 수 있다.

---

public class Main {
        // 간선 정보 저장할 edge
        static ArrayList<Integer> edge[] = new ArrayList[20001];
        // 방문여부 저장할 mark
        static boolean mark[] = new boolean[20001];
        // 0,1,0,1.. 표시
        static int mark2[] = new int[20001];

그래프를 담을 ArrayList, 방문 여부 true or false로 저장할 boolean 배열, 

정점을 0,1,0,1...로 구분할 int형 배열.

 

---

DFS

 

// Dept First Search
    static void dfs(int n) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(n); mark[n] = true;

        // 1 or 0
        int temp = 0;
        temp = 1 - temp; // 1
        mark2[n] = temp;

        while(!s.empty()) {
            int f = s.peek();
            boolean none = true;

            for(int x : edge[f]) {
                if(mark[x] == false) {
                    s.push(x); mark[x] = true;

                    temp = 1 - temp;
                    mark2[x] = temp;

                    none = false;
                    break;
                }
            }
            if(none) {
                s.pop();
                temp = 1 - temp; // pop할때도 temp값 변경 필요
            }
        }
    }

정점을 방문하면서 mark2에 0이나 1로 번갈아 가면서 기록한다. 

주의할 점은 

if(none) {
                s.pop();
                temp = 1 - temp; // pop할때도 temp값 변경 필요
            }

방문할 정점이 더 이상 없어서 pop 할 때 temp값을 한 번 더 변경해야 제대로 0,1,0,1.. 순서로 기록된다. 

 

---

isBipartite (이분 그래프인지 판단)

 

static void isBipartite(int n) {
        boolean check = true; // true면 이분그래프
        for (int i = 1; i <= n; i++) {
            int CurrentMark = mark2[i];
            boolean none = true;

            for (int x : edge[i]) {
                // 인접 정점이 같은 숫자로 mark2 되있으면
                if (mark2[x] == CurrentMark) {
                    none = false;
                    break;
                }
            }
            // 인접 정점이 같은 숫자로 mark2된게 하나라도 있으면
            if (!none) {
                System.out.println("NO");
                check = false;
                break;
            }
        }
        if (check) System.out.println("YES");
    }

모든 정점을 대상으로 간선으로 이어진 정점 중 하나라도 같은 숫자가 기록돼 있으면 이분 그래프가 아니므로 

바로 break로 탈출해도 된다. 

 

---

MAIN

 

이전 그래프 문제들과 동일하게 Array에 그래프 저장하고 DFS를 돌린다.

그런데 처음에 그냥 DFS를 돌렸더니 틀렸다고 나왔다.

알고 보니 이 문제도 분리 그래프인지 아닌지를 판단해야 했다. 

 

문제에서 "그래프가 주어졌을 때"라고 했을 때 난 그냥 쭉 이어진 하나의 그래프를 생각했는데

분리 그래프도 하나의 그래프였다. 

앞으로도 그래프가 주어졌을때 라고 하면 쭉 이어진 그래프가 아닌 분리 그래프의 가능성도 생각해야 할 것 같다. 

 

코드

import java.util.*;

public class Main {
        // 간선 정보 저장할 edge
        static ArrayList<Integer> edge[] = new ArrayList[20001];
        // 방문여부 저장할 mark
        static boolean mark[] = new boolean[20001];
        // 0,1,0,1.. 표시
        static int mark2[] = new int[20001];

    // Dept First Search
    static void dfs(int n) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(n); mark[n] = true;

        // 1 or 0
        int temp = 0;
        temp = 1 - temp; // 1
        mark2[n] = temp;

        while(!s.empty()) {
            int f = s.peek();
            boolean none = true;

            for(int x : edge[f]) {
                if(mark[x] == false) {
                    s.push(x); mark[x] = true;

                    temp = 1 - temp;
                    mark2[x] = temp;

                    none = false;
                    break;
                }
            }
            if(none) {
                s.pop();
                temp = 1 - temp; // pop할때도 temp값 변경 필요
            }
        }
    }

    static void isBipartite(int n) {
        boolean check = true; // true면 이분그래프
        for (int i = 1; i <= n; i++) {
            int CurrentMark = mark2[i];
            boolean none = true;

            for (int x : edge[i]) {
                // 인접 정점이 같은 숫자로 mark2 되있으면
                if (mark2[x] == CurrentMark) {
                    none = false;
                    break;
                }
            }
            // 인접 정점이 같은 숫자로 mark2된게 하나라도 있으면
            if (!none) {
                System.out.println("NO");
                check = false;
                break;
            }
        }
        if (check) System.out.println("YES");
    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);

        int k = s.nextInt(); // test case

        for (int z = 0; z < k; z++) {

            int n = s.nextInt(); // 정점의 개수
            int m = s.nextInt(); // 간선의 개수
            int cnt = 0;

            // 2차원 edge 생성
            for (int i = 0; i <= n; i++) {
                edge[i] = new ArrayList<Integer>();
            }

            // 간선정보 edge에 저장
            for (int i = 0; i < m; i++) {
                int t, f;
                t = s.nextInt();
                f = s.nextInt();

                edge[f].add(t);
                edge[t].add(f);
            }



            for(int i = 1; i <= n; i++) {
                if(!mark[i]) {
                    dfs(i);
                }
            }

            isBipartite(n);


            // 새로운 test case를 위해서 mark 초기화
            for(int i = 1; i <= n; i++) {
                mark[i] = false;
                mark2[i] = 0;
            }

        }
    }
}

 

---

Solution

 

코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        while(k-- > 0) {
            int n = sc.nextInt(); // vertex
            int m = sc.nextInt(); // edge

            // create vertex
            ArrayList<Integer>[] a =
                    (ArrayList<Integer>[]) new ArrayList[n + 1];

            for(int i = 1; i <= n; i++)
                a[i] = new ArrayList<Integer>();

            // write edge
            for(int i = 0; i < m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                a[u].add(v);
                a[v].add(u);
            }

            // create mark group
            int[] group = new int[n + 1];
            boolean res = true; // 이분 그래프인가?

            // DFS 탐색 및 마킹
            for(int i = 1; i <= n; i++) {
                if(group[i] == 0) { // no marking
                    dfs(a, group, i, 1); // dfs search
                }
            }

            // 마킹(grouping) 결과적으로 이분글프 여부 확인
            for(int i = 1; i <= n; i++) { // 모든 정점 확인
                for(int j : a[i]) { // 정점에 연결된 모든 간선 확인
                    if(group[i] == group[j]) { // 간선 양 정점 같은 그룹
                        res = false; // 이분그래프가 아님
                    }
                }
            }

            // 결과 출력
            System.out.println(res ? "YES" : "NO");
        }
    }

    public static void dfs(ArrayList<Integer>[] a, int[] g, int x, int c) {
        // a: vertex arrayList
        // g: group marking array
        // x: start vertex index
        // c: marking init-value(1)

        g[x] = c; // marking

        for(int y : a[x]) { // 정점에 연결된 모든 간선 탐색색
            if(g[y] == 0) dfs(a, g, y, 3-c);
        }
    }

}

일단 내 코드와 다른점은 

나는 방문 여부를 확인하기위한 mark와 숫자를 기록하기 위한 mark2를 따로 만들었다.

하지만 솔루션에선 그냥 int형 배열을 하나 만들어서 값이 0이면 방문하지 않았다고 보고 1이나 2로 마킹을 했다.

메모리 측면에서 훨씬 좋다.. 다음 테스트 케이스를 수행할 때 초기화도 두 번 하지 않아도 된다..

 

그리고 DFS를 재귀하는 형태로 만들어서 스택 컨테이너도 쓰지 않았다.