[백준 1707번] [Kotlin] 이분 그래프

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

1707번: 이분 그래프

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 이분 그래프

 

 

설명

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

이분 그래프란, 쉽게 말하자면 모든 정점을 두 개의 색깔로 칠하되,

이웃한 모든 정점의 색깔이 서로 다른 그래프 입니다.

 

방문하지 않은 모든 정점을 하나씩 DFS 탐색해 나가면서,

바로 직전 노드와 다른 색깔로 칠하고,

모든 정점에 색칠이 완료되면

다시 모든 정점을 탐색하며, 서로 이웃한 정점이 다른 색깔인지 확인합니다.

 

 

소스코드

import java.util.*

enum class COLOR {
    NOT_VISITED,
    RED,
    BLUE
}

var v = 0
lateinit var visited: Array<COLOR>
lateinit var connectedNodes: Array<ArrayList<Int>>

fun main() = with(System.`in`.bufferedReader()) {

    val sb = StringBuilder()

    // 테스트 케이스만큼 진행
    repeat(readLine().toInt()) {

        // 정점의 수, 간선의 수
        val st = StringTokenizer(readLine())
        v = st.nextToken().toInt()
        val e = st.nextToken().toInt()

        visited = Array(v + 1) { COLOR.NOT_VISITED }
        connectedNodes = Array(v + 1) { ArrayList() }

        repeat(e) {
            val st = StringTokenizer(readLine())
            val x = st.nextToken().toInt()
            val y = st.nextToken().toInt()

            connectedNodes[x].add(y)
            connectedNodes[y].add(x)
        }

        for (i in 1..v) {
            if (visited[i] == COLOR.NOT_VISITED) {
                dfs(i)
            }
        }

        // 이분 그래프인지 확인
        // 모든 정점이 이웃한 정점과 색이 다른지 (이웃 정점과 다르면 이분그래프)
        var isAble = true

        for (i in 1..v) {
            for (j in connectedNodes[i]) {
                if (visited[i] == visited[j]) {
                    isAble = false
                    break
                }
            }
            if (!isAble) break
        }

        sb.append(if (isAble) "YES\n" else "NO\n")
    }

    print(sb)
}

fun dfs(start: Int) {
    if (visited[start] == COLOR.NOT_VISITED) visited[start] = COLOR.RED

    for (i in connectedNodes[start]) {
        if (visited[i] == COLOR.NOT_VISITED) {
            visited[i] = if (visited[start] == COLOR.RED) COLOR.BLUE else COLOR.RED
            dfs(i)
        }
    }
}

 

 

코드분석

1. 색깔을 담을 Enum 클래스 COLOR - NOT_VISITED, RED, BLUE 생성

2. 정점의 개수 +1 개 만큼(0번째 인덱스는 사용하지 않으므로) ArrayList<Int>를 만들고,

연결된 정점을 ArrayList에 추가.

x와 y가 인접하다는 건, x는 y의 인접 원소이기도 하지만, y는 x의 인접원소이기도 하므로,

x.add(y), y.add(x) 둘 다 해줘야함.

3. 방문여부를 담을 visited 배열 생성 (위에서 선언한 enum-COLOR)

4. 방문하지 않은 모든 정점을 대상으로 DFS 탐색 진행

5. (DFS) 시작 노드가 방문하지 않은 노드라면, 컬러를 RED로 칠함.

6. (DFS) 인접 노드 중 방문하지 않은 노드를 하나씩 돌며,

시작 노드가 빨강이면 파랑으로, 파랑이면 빨강색으로 인접 노드를 칠함

7. 모든 정점과 이웃한 정점이 서로 다른 색깔인지 확인하며 이분그래프라면 StringBuilder에 YES, 아니라면 NO를 append

 

 

후기

처음으로 풀어보는 이분 그래프 문제입니다.

자료구조 시간때는 배웠지만, 코테로는 처음 접하기에 살짝 겁났지만,

어떻게 할지 천천히 정리해보며 막상 부딪혀보니 생각보다 어렵지 않게 풀 수 있었습니다.