백준 1707번 이분 그래프 (Java)

해결 과정

주어진 그래프가 이분 그래프인지를 판별하는 문제다. 문제의 설명에서 이분 그래프에 대한 간단한 설명이 주어지는데, 사실 이것만 읽고 이분 그래프를 이해하기가 힘들었다.

그래서 가장 먼저 이분 그래프에 대해 조사를 했다.

 

먼저 위키 백과에서 조사를 했는데, 대충 꼭짓점을 색칠한다는 걸로 나와있으나, 이분 그래프에 대한 개념이 없던 나로서는 이해하기 매우 힘든 설명이었다. 그래서 다른 블로그를 조사했고, 이분 그래프에 대해 명확한 설명이 나와있는 블로그 게시글을 봤다.

 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

이 포스팅에 따르면, 이분 그래프는 결국 전체적으로 노드를 두개의 집합으로 나누는데, 인접한 노드끼리 다른 색상을 가지면서 같은 색상의 노드끼리는 절대 인접하지 않는 그래프가 이분 그래프라고 나와있다.

 

따라서, 인접한 노드끼리 상태에 대해 검토하고, 같은 상태인지 판별하는 코드가 필요했다.

그래프를 모두 탐색하기 위해 BFS로 접근했다. 물론, 최단 거리를 구하는 것이 아니므로 DFS로 접근해도 해결할 수 있을 것으로 판단된다.

핵심 코드는 노드끼리 탐색하면서 인접한 노드는 다른 색상을 부여하고, 인접한 노드와 같은 색상인지 아닌지 판별하는 조건문과 관련된 코드다. 일반적인 BFS처럼 visited 배열외에 노드의 색상을 저장하는 배열이 추가로 필요했다.

 

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static LinkedList<Integer>[] adjList;
    static boolean[] visited;
    static int[] color;

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

        int n = scanner.nextInt();

        for (int i=0; i<n; i++) {
            int v = scanner.nextInt();
            int e = scanner.nextInt();
            adjList = new LinkedList[v+1];
            visited = new boolean[v+1];
            color = new int[v+1];

            for (int j=1; j<=v; j++) {
                adjList[j] = new LinkedList<>();
            }

            for (int j=0; j<e; j++) {
                int start = scanner.nextInt();
                int end = scanner.nextInt();

                adjList[start].add(end);
                adjList[end].add(start);
            }

            boolean result = true;

            for (int w=1; w<=v; w++) {
                if (!visited[w]) {
                    result = bfs(w);
                }

                if (!result) {
                    break;
                }
            }

            if (!result) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }

    static boolean bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean isBipartite = true;
        queue.add(start);
        visited[start] = true;
        // color white
        color[start] = 1;

        while (!queue.isEmpty()) {
            Integer num = queue.poll();

            Iterator<Integer> iterator = adjList[num].iterator();
            while (iterator.hasNext()) {
                Integer cur = iterator.next();
                if (!visited[cur]) {
                    // 인접 노드에 대해 방문하지 않은 경우
                    visited[cur] = true;
                    // 반대 색상을 입력한다
                    color[cur] = 1 - color[num];
                    queue.add(cur);
                } else {
                    if (color[cur] == color[num]) {
                        isBipartite = false;
                        break;
                    }
                }
            }
        }

        return isBipartite;
    }
}