[백준/BOJ] 12893번: 적의 적

문제

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

12893번: 적의 적

해설

A와 B가 적대 관계고 B와 C가 적대 관계라면, A와 C는 우호 관계가 된다.

이 때, C와 D가 적대 관계라면, A와 C가 우호 관계이고, B와 D가 우호 관계가 된다.

결론은 두개의 팀으로 나눈다는 것이다. 즉, 이분 그래프가 성립이 되는지 안되는지를 구하는 것이다.

이분 그래프의 설명은 이 글을 참고하면 좋다.

코드

import java.util.*
import kotlin.collections.ArrayList

private lateinit var graph: Array<ArrayList<Int>>

fun main() = with(System.`in`.bufferedReader()) {
    val (humanCnt, hostility) = readLine().split(" ").map { it.toInt() }
    graph = Array(humanCnt + 1) { ArrayList() }
    repeat(hostility) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        graph[a].add(b)
        graph[b].add(a)
    }

    if(bipartiteGraph(humanCnt)) println(1)
    else println(0)
}

private fun bipartiteGraph(n: Int): Boolean {
    val que: Queue<Int> = LinkedList()
    que.add(1)

    val team = IntArray(n + 1)

    for(i in 1 .. n) {
        if(team[i] == 0) {
            que.add(i)
            team[i] = 1
        }

        while (que.isNotEmpty()) {
            val cur = que.poll()
            val curTeam = team[cur]

            for (j in graph[cur].indices) {
                val nextHuman = graph[cur][j]
                val nextHumanTeam = team[graph[cur][j]]

                if (nextHumanTeam == 0) que.add(nextHuman)
                if (nextHumanTeam == curTeam) return false

                if (curTeam == 1 && nextHumanTeam == 0) team[graph[cur][j]] = 2
                else if (curTeam == 2 && nextHumanTeam == 0) team[graph[cur][j]] = 1
            }
        }
    }

    return true
}