[99클럽 코테 스터디 9일차 TIL / 백준] 1707 - 이분 그래프 (JAVA)

99클럽 코테스터디 9일차 TIL  
KeyWord : BFS, DFS, Bipartite Graph

문제

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

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

입력

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

출력

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

 

---

 

풀이

다 풀어놓고 이상한 부분에서 애 먹어서 오래 걸렸던 문제다. 문제 자체는 이분 그래프가 무엇인지만 알고 있으면 쉽게 풀 수 있다.

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

문제에서부터 이렇게 이분 그래프가 무엇인지 설명해주고 있지만... 사실 이 문장만 봐서는 잘 이해가 가지 않았다.

이 그림을 보면 쉽게 이해할 수 있다. 즉, 두 가지 색만을 이용해 인접한 노드끼리 모두 다른 색으로 칠할 수 있으면 그것을 이분 그래프라고 한다.

기존의 BFS나 DFS를 할 때 사용하던 visited배열을 살짝 변형하여 사용하는 방식으로 구현을 했다.

• 방문하지 않은 정점 : 0
• 방문한 정점 : 1, -1

이렇게 1, -1로 구분하여 탐색을 진행하면서 인접한 정점끼리 같은 색(여기서는 같은 숫자)이라면 이분 그래프가 아닌 것으로 판단하고 false를 반환한다. false를 반환하지 않고 끝까지 탐색이 진행된다면 이분 그래프라는 것이므로 true를 반환한다.

탐색은 BFS, DFS 둘 다 가능하다. 어차피 모든 노드를 방문해가며 확인해야 하므로 소요되는 시간도 차이가 없을 것이다. 물론, 구현 방법에 따라 오버헤드가 있을 수는 있지만 이론적으로는 그렇다.

이런 아이디어를 가지고 구현을 했으나...

 

첫 번째 실패 : 메모리 초과

큐 때문에 그런 건가 싶어서 이리저리 수정해보았지만, 해결되지 않았다. 그래서 조금 쉬다가 코드를 처음부터 살펴보고 무엇 때문인지 알 수 있었다.

인접 행렬 방식 때문이다.

인접 행렬로 그래프를 저장할 경우, 그 크기는 $V^2$이 된다.

이 문제 기준 $V$의 최댓값은 $20,000$이다. 인접행렬 그래프를 boolean으로 선언한다고 하더라도 $1byte \times 20000^2 = 400MB$가 된다. 문제의 메모리 제한인 256MB를 가뿐히 초과한다.

그렇기에 이 부분을 인접 리스트로 수정해주었다. 인접 리스트는 $V \times E$이므로 인접행렬 보다 효율적으로 메모리를 활용할 수 있다.

인접 행렬이 간단해서 매번 아무 생각 없이 사용해왔더니 일어났던 참사였다.

 

두 번째 실패

이번에는 그냥 '틀렸습니다'가 나왔다. 가만히 고민해보니 색칠할 때의 로직을 이상하게 짜놔서 그랬던 것이었다. (평소에는 없던 주석문이 있는 이유)

천천히 생각을 정리해가며 로직을 다시 구상해 코드를 수정해주니 성공했다.

---

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  

public class Main {  
    static int V, E;  
    static List<List<Integer>> graph;  

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

        int K = Integer.parseInt(br.readLine());  
        for (int i = 0; i < K; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            V = Integer.parseInt(st.nextToken());  
            E = Integer.parseInt(st.nextToken());  

            if(V == 1) {  
                sb.append("YES").append("\n");  
                continue;  
            }  

            graph = new ArrayList<>();  
            for (int j = 0; j < V + 1; j++) {  
                graph.add(new ArrayList<>());  
            }  

            for (int j = 0; j < E; j++) {  
                st = new StringTokenizer(br.readLine());  

                int n1 = Integer.parseInt(st.nextToken());  
                int n2 = Integer.parseInt(st.nextToken());  

                graph.get(n1).add(n2);  
                graph.get(n2).add(n1);  
            }  

            sb.append(bfs() ? "YES" : "NO").append("\n");  
        }  
        System.out.println(sb);  
    }  

    static boolean bfs() {  

        Queue<Integer> q;  
        int[] visited = new int[V + 1];  

        for (int i = 1; i <= V; i++) {  
            // 이미 방문한 노드라면 무시  
            if (visited[i] != 0)  
                continue;  

            q = new LinkedList<>();  
            q.add(i);  

            visited[i] = 1;  

            // BFS  
            while (!q.isEmpty()) {  
                int node = q.poll();  
                for (Integer next_node : graph.get(node)) {  
                    // 방문하지 않은 정점이면  
                    if (visited[next_node] == 0) {  
                        // 노드 색칠
                        visited[next_node] = visited[node]*-1;  
                        q.add(next_node);  
                    }  
                    // 이분 그래프가 아니라면 (인접한 노드의 색과 자신으 색이 같다면)  
                    else if (visited[next_node] == visited[node]) {  
                        return false;  
                    }  
                }  
            }  
        }  

        return true;  
    }  
}