[백준/BOJ] 1707번: 이분 그래프

문제

https://www.acmicpc.net/problem/1707

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
}