Daily LeetCode Challenge - 785. Is Graph Bipartite?

Problem From.

https://leetcode.com/problems/is-graph-bipartite/

오늘 문제는 그래프가 주어졌을때, 그 그래프가 bipartite 그래프인지 아닌지 판별하는 문제였다.
그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 그래프를 색칠할때, 변으로 이어져있는 이웃한 노드가 같은 색깔이면 이분 그래프가 아니게 된다.

이 문제는 DFS 를 이용하여 풀 수 있었는데, 시작노드에서 탐색해나가면서, 선으로 이어진 이웃한 노드를 각각 다른 색깔로 칠해나간다. 먼저 빨강을 칠했다면 그 다음 파랑을 칠하는 식으로 이어나가다가, 탐색이 끝난다음, 각각 노드의 이웃에 같은 색이 있는지 검사하면 된다.

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val nodes = (0 until graph.size).map { it to GraphNode(it, graph[it].toList()) }.toMap()
        nodes.values.forEach { dfs(nodes, it, Color.RED) }
        return nodes.flatMap { node -> node.value.neighbors.map { node.key to it } }
            .all { nodes[it.first]!!.color!! != nodes[it.second]!!.color!! }
    }

    private fun dfs(nodes: Map<Int, GraphNode>, node: GraphNode, color: Color) {
        if (node.color != null) return
        node.color = color
        node.neighbors.forEach { dfs(nodes, nodes[it]!!, if (color == Color.RED) Color.BLUE else Color.RED) }
    }
}

data class GraphNode(val id: Int, val neighbors: List<Int>, var color: Color? = null)

enum class Color { RED, BLUE }