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

해당 문제는 DFS 혹은 BFS를 이용하여 풀 수 있었습니다.

해당 문제를 풀기에 앞서 가장 핵심 개념은 방문했던 노드와 현재의 노드의 값이 같다면 이분그래프가 아니라는 것 입니다.

 

저의 경우에는 BFS를 이용하여 작성하였으며, 큐에 넣기전 다음 노드의 값이 0 일 때 큐에 추가하고, 해당 노드의 값을 현재 노드의 값 *-1 를 하여 구분을 짓게 하였습니다. 그리고 만약 0 이 아니라면 다음 노드의 값과 현재노드의 값이 동일한 지 확인하였고 동일할 경우 반복문을 중지 및 BufferedWriter 에 "No"를 입력하였습니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var K = st.nextToken().toInt()

    repeat(K){
        st = StringTokenizer(br.readLine())
        val V = st.nextToken().toInt()
        val E = st.nextToken().toInt()
        val arr = Array(V+1,{ArrayList<Int>()})
        repeat(E){
            st = StringTokenizer(br.readLine())
            val one = st.nextToken().toInt()
            val two = st.nextToken().toInt()
            arr[one].add(two)
            arr[two].add(one)
        }

        val red = 1
        var check = true
        var visit = IntArray(V+1){0}
        for(i in 1 .. V){
            if(visit[i] != 0) continue
            var dq = ArrayDeque<Int>()
            dq.addFirst(i)
            visit[i] = red
            while(!dq.isEmpty()){
                val now = dq.poll()
                for(j in 0 .. arr[now].size-1){
                    if(visit[arr[now][j]] == 0){
                        visit[arr[now][j]] = (visit[now] * -1)
                        dq.addLast(arr[now][j])
                    } else if(visit[arr[now][j]].equals(visit[now])){
                        check = false
                        break
                    }
                }
                if(!check) break
            }
        }
        if(!check){
            bw.appendLine("NO")
        } else {
            bw.appendLine("YES")
        }

    }

    bw.flush()
    bw.close()

}