코틀린 코딩테스트 강좌, 이분 그래프 판별하기

문제 설명

주어진 그래프가 이분 그래프인지 판별하는 문제입니다. 이분 그래프란 그래프의 정점들을 두 개의 집합으로 나눌 수 있어, 같은 집합에 속하는 정점들 간에는 간선이 존재하지 않는 그래프를 의미합니다.
즉, 어떤 정점 u와 v가 연결되어 있을 경우, u와 v는 서로 다른 집합에 속해야 합니다.

입력

• 정수 n (1 ≤ n ≤ 1000): 정점의 수
• 정수 m (1 ≤ m ≤ 5000): 간선의 수
• m개의 쌍 (u, v): 정점 u와 정점 v 간의 간선 정보

출력

그래프가 이분 그래프이면 YES를, 그렇지 않으면 NO를 출력합니다.

문제 해결 과정

이분 그래프 판별을 위해 DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 사용할 수 있습니다. 그래프의 정점들을 두 개의 색으로 칠해가며 진행하며, 인접한 정점이 같은 색으로 칠해지면 이분 그래프가 아닙니다.

1단계: 그래프 표현

그래프는 인접 리스트로 표현합니다. 정점 간의 연결 관계를 저장하기 위해 ArrayList를 사용합니다.

2단계: 그래프 탐색

DFS 또는 BFS를 사용하여 그래프를 탐색하면서 각 정점의 색을 정하고, 인접한 정점의 색과 비교하여 이분 그래프인지 판별합니다.

3단계: 구현

아래는 코틀린으로 구현한 코드입니다.

fun isBipartiteGraph(n: Int, edges: List>): String {
    val graph = Array(n + 1) { mutableListOf() }
    for (edge in edges) {
        graph[edge.first].add(edge.second)
        graph[edge.second].add(edge.first)
    }

    val color = IntArray(n + 1) { -1 } // -1: 미방문, 0: 집합0, 1: 집합1

    fun bfs(start: Int): Boolean {
        val queue: Queue = LinkedList()
        queue.add(start)
        color[start] = 0 // 시작 정점을 집합0으로 칠하기

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            for (neighbor in graph[node]) {
                if (color[neighbor] == -1) { // 방문하지 않은 정점
                    color[neighbor] = 1 - color[node] // 현재 정점의 색과 반대 색으로 칠하기
                    queue.add(neighbor)
                } else if (color[neighbor] == color[node]) {
                    return false // 인접한 정점이 같은 색일 경우
                }
            }
        }
        return true
    }

    for (i in 1..n) {
        if (color[i] == -1) { // 미방문 정점일 경우 BFS 시작
            if (!bfs(i)) {
                return "NO"
            }
        }
    }
    return "YES"
}

// 사용 예
fun main() {
    val n = 5 // 정점 수
    val edges = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5)) // 간선 정보
    println(isBipartiteGraph(n, edges)) // 출력: YES
}

4단계: 결과 및 검증

위 코드를 실행하면 그래프가 이분 그래프인지 판단할 수 있습니다. 다양한 그래프를 테스트하여 올바른 결과를 도출하는지 검증합니다.

결론

본 강좌를 통해 이분 그래프의 개념과 판별 방법을 이해하고, 코틀린 프로그래밍을 통해 이 문제를 효과적으로 해결하는 방법을 배웠습니다.