(Kotlin) 백준 1707 - 이분 그래프

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

1707번: 이분 그래프

 

풀이

그래프의 모든 노드를 인접한 노드와 같은 집합에 속하지 않도록 하면서, 두 집합으로 분할할 수 있는지 판별하는 문제이다.

 

먼저 노드를 두 집합으로 분할해야 하므로, 모든 노드를 방문하면서 어떤 집합에 속할 것인지를 정해준다. 분할하는 것을 쉽게 색칠한다고 표현하자. DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 인접 노드를 현재 노드와 다른 색으로 색칠하면 된다. 나는 colors라는 배열을 만들어서 모든 노드를 0과1로 나누었다. 

 

얼핏 단순하게 "인접 노드를 모두 다른 색으로 칠하면 무조건 이분 그래프로 만들 수 있는 거 아닌가?"라고 생각할 수도 있지만, 인접노드가 이미 이전에 방문되었고, 현재 노드와 같은 색으로 칠해진 경우가 발생할 수 있다.

  

분할이 끝나면 그래프에서 모든 노드를 돌면서 자신과 같은 색인 인접노드가 있는지 확인해주면 이분 그래프인지 아닌지 판별할 수 있다.

 

참고로 연결 그래프라면 DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 이분 그래프 여부를 판별할 수 있으며, 연결 그래프가 아니라면 위에 언급한 대로 노드마다 인접 노드를 검사해주면 된다.

 

이를 좀 더 구체적으로 적으면 다음과 같다.  

1. DFSorBFS를 사용해서 모든 노드를 한번씩 방문한다.

2. 노드마다 인접 노드와 다른 색으로 칠해준다. 

3. 노드마다 인접 노드를 확인해서 같은 색으로 칠한 노드가 있으면 "NO", 없으면 "YES"를 출력한다.

      

 

코드

fun main(){
    for(i in 0 until readLine()!!.toInt()){
        var numberOfNode = 0
        var numberOfEdge = 0
        readLine()!!.split(" ").let{
            numberOfNode = it[0].toInt()
            numberOfEdge = it[1].toInt()
        }

        val visit = Array(numberOfNode){false}
        val colors = Array(numberOfNode){-1}
        val graph = Array(numberOfNode){mutableListOf<Int>()}
        // 인접리스트로 그래프 저장
        for(i in 0 until numberOfEdge){
            readLine()!!.split(" ").map{it.toInt()-1}.let{
                graph[it[0]].add(it[1])
                graph[it[1]].add(it[0])
            }
        }

	// DFS로 모든 노드 방문
        (0 until numberOfNode).forEach { node ->
            if (!visit[node]){
                visit[node] = true
                colors[node] = 0	// 첫 노드를 0으로 색칠
                dfs(graph, node, visit, colors)
            }
        }

	// 모든 노드마다 인접 노드가 무슨 색인지 확인한다
        if (isBipartite(graph, colors)){
            println("YES")
            continue
        }
        println("NO")
    }
}

fun isBipartite(graph: Array<MutableList<Int>>, colors: Array<Int>): Boolean{
    graph.indices.forEach { node ->
        graph[node].forEach { adjacent ->
            if (colors[node] == colors[adjacent]){	// 현재 노드와 인접노드의 색이 같으면 false
                return false
            }
        }
    }

    return true
}

fun dfs(graph: Array<MutableList<Int>>, node: Int, visit: Array<Boolean>, colors: Array<Int>){
    graph[node].forEach { toNode ->
        if (!visit[toNode]){
            visit[toNode] = true
            colors[toNode] = (colors[node]+1) % 2	// 인접노드를 현재 노드와 다른 색(0,1)으로 칠한다
            dfs(graph, toNode, visit, colors)
        }
    }
}

 

리뷰

이분그래프에 대해 알고 있고, DFS와 BFS를 쓸 줄 아는지 묻는 문제였던 것 같다.