[백준 1707] 이분 그래프

문제

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

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

입력

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

출력

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

---

 

풀이

처음에 문제 이해가 되지 않아 이분 그래프에 대해 찾아보았다

이분 그래프는 노드들을 2개의 그룹으로 나누었을 때 각 그룹에 속해있는 노드들이 서로 인접하지 않은 경우를 말한다

 

A = {1, 3, 5}

B = {2, 4, 6}

을 가정했을 때 노드 1은 그룹 B에 속한 노드 2,4,6과는 인접할 수 있다

즉 1-2, 1-4, 1-6은 가능하지만 노드 1이 속해있는 그룹 A의 노드 3,5와는 인접할 수 없는 관계이다

1-3 또는 1-5 간선이 있다면 이분 그래프가 아닌 것이다

 

DFS

그렇다면 주어진 그래프가 이분 그래프가 될 수 있는지 판단하기 위해서 다음과 같이 할 수 있다

1. dfs로 모든 노드를 방문
2. 첫 방문인 경우 자신을 호출한 노드와 다른 그룹 식별자 번호를 부여
3. 현재 노드와 인접한 모든 노드들의 그룹 식별자 번호를 비교
4. 식별자 번호가 같은 경우가 하나라도 있을시 이분 그래프 성립 x

static void dfs(int node, int group) {
        visit[node] = true;
        if (groups[node] == 0) {
            groups[node] = group;
        }
        for (int nextNode : R[node]) {
            if (groups[node] == groups[nextNode]) {
                res = "NO";
                return;
            }
            if (!visit[nextNode]) {
                dfs(nextNode, groups[node] == GROUP_A ? GROUP_B : GROUP_A);
            }
        }
        visit[node] = false; // 방문했던 노드의 방문 기록을 지워 다른 방문루트도 탐색
}

 

처음에는 위 코드와 같이 dfs탐색의 유연성을 부여했다가 시간초과가 났다

방문했던 노드의 방문기록을 지워 모든 방문방법(순서)를 탐색하게되니 시간이 더 걸릴수밖에 없다

 

하지만 이 문제에서는 dfs의 방문방법(순서)와 상관없이 처음 노드들을 방문하는 과정에서 식별 번호를 매겨둔다면 이것만으로도 이분 그래프를 판단할 수 있기에 다음과 같이 수정하였다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Boj1707 {
    static final int GROUP_A = 1;
    static final int GROUP_B = 2;
    static int K, V, E, v1, v2;
    static ArrayList<Integer>[] R;
    static boolean[] visit;
    static int[] groups;
    static String res;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        K = Integer.parseInt(br.readLine());

        for (int testcase = 0; testcase < K; testcase++) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            R = new ArrayList[V + 1];
            visit = new boolean[V + 1];
            groups = new int[V + 1];
            res = "YES";
            for (int numOfVertices = 0; numOfVertices <= V; numOfVertices++) {
                R[numOfVertices] = new ArrayList<>();
            }
            for (int numOfEdge = 0; numOfEdge < E; numOfEdge++) {
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken());
                v2 = Integer.parseInt(st.nextToken());
                R[v1].add(v2);
                R[v2].add(v1);
            }
            for (int edge = 1; edge <= V; edge++) {
                if (!visit[edge]) {
                    dfs(edge, GROUP_A);
                }
            }
            System.out.println(res);
        }
    }

    static void dfs(int node, int group) {
        visit[node] = true;
        if (groups[node] == 0) {
            groups[node] = group;
        }
        for (int nextNode : R[node]) {
            if (groups[node] == groups[nextNode]) {
                res = "NO";
                return;
            }
            if (!visit[nextNode]) {
                dfs(nextNode, groups[node] == GROUP_A ? GROUP_B : GROUP_A);
            }
        }
    }
}

 

문제를 푸는 과정에서 bfs로 풀면 더 편하겠다고 생각했다

 

그래서 bfs로도 풀어볼 예정

---

BFS

루트 노드부터 한 계단씩 전진하며 인접 노드를 훑는 bfs가 이분 그래프를 판단하는데에 더 직관적인 느낌이 들어서 풀어보았다

1.  루트 노드 (검사 시작 노드)에 그룹 식별번호를 부여하고 큐에 넣는다
2. 큐의 첫 원소를 빼서 해당 원소의 방문 여부를 체크하고 인접 노드들을 전부 검사한다
3. 인접 노드를 검사하는 과정에서 아직 방문이 안된 노드는 큐에 집어넣고 현재 노드와 다른 그룹 식별번호를 부여한다
4. 만약 인접 노드를 검사하는 과정에서 현재 노드와 인접 노드의 그룹 식별번호가 같다면 결과를 NO로 수정하고 리턴
5. 큐가 빌 때까지 위 과정을 반복

    static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        visit[node] = true;
        groups[node] = GROUP_A;

        while(!q.isEmpty()) {
            int currentNode = q.poll();
            visit[currentNode] = true;
            for (int nextNode : R[currentNode]) {
                if (groups[currentNode] == groups[nextNode]) {
                    res = "NO";
                    return;
                }
                if (!visit[nextNode]) {
                    groups[nextNode] = groups[currentNode] == GROUP_A ? GROUP_B : GROUP_A;
                    q.offer(nextNode);
                }
            }
        }
    }

 

dfs와 비교했을 때 시간은

 

일반적으로 bfs가 더 빠르다고 알고있지만 결과는 dfs가 더 빠르게 나온다

유의미한 정도의 속도 차이는 아니지만 이분 그래프를 탐색하는 로직에 있어서는 테스트케이스에 따라 dfs가 더 빠를 수 있겠다는 생각도 든다