자바 코딩테스트 강좌, 이분 그래프 판별하기

이 글에서는 ‘이분 그래프’에 대한 개념과 이를 판별하는 알고리즘 문제를 다룰 것입니다. 이분 그래프란 그래프의 정점을 두 개의 집합으로 나누어, 서로 다른 집합에 속한 정점들 사이에만 간선이 있는 그래프를 말합니다. 이러한 그래프는 다양한 문제에 응용될 수 있으며, 특히 이분 매칭과 같은 알고리즘에서 핵심적인 역할을 합니다.

1. 문제 정의

다음은 이분 그래프를 판별하는 문제의 예시입니다:


문제: 이분 그래프 판별하기

입력: 
- 첫째 줄에 정점의 수 N과 간선의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000)
- 다음 M개의 줄에 각 간선의 두 정점 u와 v가 주어진다. (1 ≤ u, v ≤ N)

출력:
- 이분 그래프일 경우 "Yes", 아니면 "No"를 출력한다.

2. 이분 그래프란?

이분 그래프는 특정한 조건 아래에서 정점을 나눌 수 있는 그래프 구조입니다. 즉, 그래프의 모든 두 정점 u와 v가 간선으로 연결되어 있다면, u와 v는 서로 다른 집합에 속해야 합니다. 이러한 성질로 인해 이분 그래프는 2색으로 칠할 수 있다는 특성이 있습니다. 즉, 한 집합에 속하는 정점들은 모두 같은 색으로 칠해지고, 다른 집합에 속하는 정점들은 다른 색으로 칠해집니다.

3. 알고리즘 접근법

이분 그래프를 판별하는 방법은 다음과 같습니다. DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 그래프를 탐색하며 각 정점에 색을 칠해 가는 방식으로 진행됩니다.

그래프를 인접 리스트로 표현합니다.
모든 정점에 대해 방문하지 않은 정점이 있다면, 해당 정점에서 BFS 또는 DFS를 시작합니다.
시작 정점에 색을 할당하고, 인접한 정점들에게는 다른 색을 할당하면서 탐색을 진행합니다.
만약 인접한 정점이 이미 방문했으며, 같은 색을 가지고 있다면 이분 그래프가 아님을 판별합니다.
모든 정점의 탐색이 끝나면 이분 그래프 여부를 판단하여 결과를 출력합니다.

4. 자바 코드 구현

아래는 위의 알고리즘을 기반으로 구현한 자바 코드입니다:


import java.util.*;

public class BipartiteGraph {
    static List> graph;
    static int[] color;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        color = new int[N + 1];
        boolean isBipartite = true;
        
        for (int i = 1; i <= N; i++) {
            if (color[i] == 0) {
                if (!bfs(i)) {
                    isBipartite = false;
                    break;
                }
            }
        }
        
        System.out.println(isBipartite ? "Yes" : "No");
    }
    
    private static boolean bfs(int start) {
        Queue queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 1; // 시작 정점에 색칠
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (color[neighbor] == 0) {
                    // 인접 정점이 방문하지 않았다면
                    color[neighbor] = 3 - color[node]; // 색을 반대로 칠함
                    queue.offer(neighbor);
                } else if (color[neighbor] == color[node]) {
                    // 인접 정점이 같은 색이라면
                    return false;
                }
            }
        }
        return true;
    }
}

5. 코드 설명

위의 자바 코드는 이분 그래프 판별을 위한 알고리즘을 구현한 것입니다. 각 부분을 자세히 살펴보겠습니다.

5.1 그래프 표현

그래프는 List> 형태의 인접 리스트로 표현하였습니다. 각 정점의 목록을 저장하고, 간선 정보를 추가하여 그래프 구조를 완성합니다.

5.2 색 배열

색 배열 color는 각 정점의 색을 관리합니다. 0은 방문하지 않음을, 1과 2는 서로 다른 색을 나타냅니다.

5.3 BFS 탐색

bfs 메서드는 BFS 알고리즘을 사용하여 그래프를 탐색합니다. 시작 정점을 큐에 추가하고, 방문한 정점에 색을 칠합니다. 이후 인접 정점에 대해 색을 할당하며 충돌 여부를 체크합니다. 만약 같은 색을 가진 정점이 발견되면 그 그래프는 이분 그래프가 아닙니다.

6. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N + M)입니다. 여기서 N은 정점의 수, M은 간선의 수를 의미합니다. 그래프의 모든 정점과 간선을 한 번씩 탐색하기 때문입니다.

7. 기타 고려사항

이 알고리즘은 연결 그래프와 비연결 그래프 모두에 대응할 수 있습니다. 비연결 그래프의 경우 각 연결 요소를 독립적으로 검사하여 이분 그래프 판별을 수행합니다.

8. 결론

이 글에서는 이분 그래프를 판별하는 문제를 다루었습니다. 이러한 문제는 많은 경우에 사용되며, 특히 알고리즘 면접 준비에 유용합니다. 이분 그래프에 대한 이해를 통해 더 나아가 다양한 그래프 문제를 해결하는 데 도움을 줄 것입니다. 지속적인 연습과 다양한 문제 풀이를 통해 코딩 실력을 향상시키는 것을 추천드립니다.