[알고리즘] 이분 그래프(Bipartite Graph)

이분 그래프란?

정점을 두 그룹으로 나눌 수 있으면서, 같은 그룹끼리는 간선으로 이어지지 않은 그래프이다.

트리가 아닌 그래프이므로, 사이클이 있어도 상관없으나, 같은 색상의 정점끼리 연결은 있어서는 안된다.

간선이 단 한도 없고 정점만 있는 상태도 이분 그래프이다. 여기에서 알 수 있듯이, 모든 정점이 꼭 연결되있어야 하는 것이 아니다.

이분 그래프 구현

이분 그래프는 DFS 또는 BFS를 사용하여 구현할 수 있다.

나는 BFS가 더 익숙하여 BFS를 사용할 것이다.

백준의 1707번 이분 그래프 문제를 예시로 들어보자.

import java.util.*
import kotlin.collections.ArrayList

private lateinit var color: IntArray
private lateinit var graph: Array<ArrayList<Int>>

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val (nodeCnt, edgeCnt) = readLine().split(" ").map { it.toInt() }
        graph = Array(nodeCnt + 1) { ArrayList() }
        color = IntArray(nodeCnt + 1)

        repeat(edgeCnt) {
            val (from, to) = readLine().split(" ").map { it.toInt() }
            graph[from].add(to)
            graph[to].add(from)
        }

        if(bipartiteGraph(nodeCnt)) println("YES")
        else println("NO")
    }
}

private fun bipartiteGraph(n: Int): Boolean {
    val que: Queue<Int> = LinkedList()

    for(i in 1 ..n) {
        if(color[i] == 0) {
            que.add(i)
            color[i] = 1
        }

        while(que.isNotEmpty()) {
            val cur = que.poll()
            val curColor = color[cur]

            for(j in graph[cur].indices) {
                val nextColor = color[graph[cur][j]]
                if(nextColor == 0) que.add(graph[cur][j])
                if(nextColor == color[cur]) return false
                if(curColor == 1 && nextColor == 0) color[graph[cur][j]] = 2
                else if(curColor == 2 && nextColor == 0) color[graph[cur][j]] = 1
            }
        }
    }

    return true
}