[백준] 3098번 소셜네트워크(그래프, 브루트포스)[Kotlin - 코틀린]

백준 3098번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

3098번: 소셜네트워크

문제

문제 접근

친구관계는 양방향 그래프로 저장되고, 친구의 친구는 친구입니다.
처음에 입력받은 친구관계로부터 모두가 친구가 될 때까지 하루에 새로운 친구관계가 얼마나 생기는 지 구하면 되는 문제입니다!
입력값의 범위가 굉장히 작으므로 완전탐색으로 양방향 그래프를 탐색하고 조건에 맞춰 갱신해주었습니다!

모두 친구가 될 때까지 반복을 하며,
모든 인원의 친구리스트를 순차탐색하며, 친구리스트에 있는 친구들의 친구리스트도 순차탐색을 합니다.
만약 친구리스트에 있는 친구의 친구가 나와 친구가 아니라면, 새로운 친구(새로운 관계)가 될 수 있으므로 새 친구 관계로 저장을 해둡니다.(즉각 반영하면 Exception in thread "main" java.util.ConcurrentModificationException 발생)

친구 관계는 Pair(1,4)와 같은 형식으로 저장이되는데, Pair(1, 4) / Pair(4, 1)은 동일한 친구 관계를 나타내므로 Pair로 친구 관계를 저장할 때 무조건 작은 수, 큰 수 순서로 배치하였고 Set을 사용하여 중복 관계를 방지하였습니다.

정답 코드

package hyunsoo.`3week`

/**
 * 친구의 친구는 나의 친구
 * A와 B의 친구라면 B도 A의 친구?.. 말이 왜이래?
 *
 * 입/출력
 * - 첫째 줄
 *      - 사람의 수 N(1 ~ 50)과 처음 친구 관계의 수 M(1 ~ n * (n-1)/ 2)이 주어짐.
 * - 둘째 줄부터 M개의 줄
 *      - 두 정수 A, B (1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B)
 *
 * 아이디어
 * - 양방향 그래프이므로 2차원 배열을 사용하고 [a] = b / [b] = a 형식으로 그래프 정보를 저장
 * - 매번 친구관계들을 모두 확인해서 친구로 저장
 * - 새로운 친구 관계 판정은 어떻게 해야할까
 *      - 관계를 Pair로 묶은 후 Set을 통해 관리하고 한 번에 계산하자!
 *      - 그렇지 않고 반복문 내부에서 리스트를 직접 조작하면 Exception in thread "main" java.util.ConcurrentModificationException 빌셍
 */


fun main() {

    val (n, m) = readln().split(" ").map { it.toInt() }

    // 친구 관계 데이터가 담길 그래프
    val friendDataGraph = Array(n + 1) { mutableListOf<Int>() }
    // 새로운 관계를 임시로 담을 리스트
    val newRelationShipList = mutableSetOf<Pair<Int, Int>>()
    // - 하루마다 생성되는 친구 관계의 수 - 정답
    val madeRelationShipCntList = mutableListOf<Int>()

    repeat(m) {
        val (a, b) = readln().split(" ").map { it.toInt() }
        friendDataGraph[a].add(b)
        friendDataGraph[b].add(a)
    }

    // 모두가 친구가 돨 때까지!
    while (isEveryoneFriend(friendDataGraph, n - 1).not()) {
        // 친구 관계도를 순차 탐색
        friendDataGraph.forEachIndexed { target, targetfriendList ->

            // 타겟의 친구들을 순차 탐색
            targetfriendList.forEach { myfriend ->

                // 타겟의 친구의 친구들을 순차 탐색
                friendDataGraph[myfriend].forEach { friendOfFriend ->
                    // 친구의 친구가 친구가 아니었다면
                    if ((friendOfFriend in targetfriendList).not() && target != friendOfFriend) {
                        // 새로운 관계(새 친구)!
                        val newRelationShip = makeSortedRelationShip(target, friendOfFriend)
                        newRelationShipList.add(newRelationShip)
                    }
                }
            }
        }

        // 새로운 관계 적용
        newRelationShipList.forEach { relationShipData ->
            val (a, b) = relationShipData
            friendDataGraph[a].add(b)
            friendDataGraph[b].add(a)
        }
        // 하루마다 만들어지는 새로운 관계의 수를 저장
        madeRelationShipCntList.add(newRelationShipList.size)
        // 새로운 관계를 모두 적용했으므로 초기화
        newRelationShipList.clear()

    }

    // 정답형식에 맞게 출력
    madeRelationShipCntList.apply {
        println(this.size)
        this.forEach {
            println(it)
        }
    }


}

// 더 작은 순서가 앞으로 나오게
fun makeSortedRelationShip(who: Int, andWho: Int) =
    if (who < andWho) Pair(who, andWho) else Pair(andWho, who)

// 모두가 친구인가?
fun isEveryoneFriend(friendDataGraph: Array<MutableList<Int>>, friendCnt: Int): Boolean {

    friendDataGraph.forEachIndexed { index, friendList ->
        if (index != 0 && friendList.size != friendCnt) return false
    }

    return true
}