9466번: 텀 프로젝트 - Kotlin (BFS)

9466번: 텀 프로젝트

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

나의 풀이 - 1차

 이 문제는 그래프 탐색을 이용해서 해결해야 하는 문제이다. 나는 처음 이 문제를 풀 때,  1번 학생부터 n번 학생까지 그 학생부터 시작하는 팀을 꾸렸고 만약 팀이 완성 되었다면 그 팀에 속한 학생들을 전부 check해서 그 학생부터는 탐색하기 않게 했다. 다만 이 알고리즘은 O(N²)의 시간 복잡도를 가졌음으로 시간 초과가 나고 말았다.

import java.util.LinkedList
import java.util.Queue

fun main() = with(System.`in`.bufferedReader()) {
    val t = readLine().toInt()
    val test = mutableListOf<Pair<Int, MutableList<Int>>>()

    repeat(t) {
        val n = readLine().toInt()
        val num = readLine().split(" ").map { it.toInt() }.toIntArray()
        val temp = mutableListOf<Int>().apply { add(0) }
        num.map { temp.add(it) }
        test.add(n to temp)
     }

    test.forEach {
        println(bfs(it.first, it.second))
    }
}

fun bfs(n: Int, num: MutableList<Int>): Int {
    var cnt = 0

    val student = BooleanArray(n + 1)

    for (i in 1..n) {
        if (!student[i]) {
            val visited = BooleanArray(n + 1)
            val queue : Queue<Int> = LinkedList()
            val team = mutableListOf<Int>()
            queue.add(i)
            team.add(i)
            visited[i] = true

            while (queue.isNotEmpty()) {
                val now = queue.poll()
                if (num[now] == i) {
                    cnt += team.size
                    team.forEach{ student[it] = true }
                }
                else {
                    if (!visited[num[now]]) {
                        visited[num[now]] = true
                        queue.add(num[now])
                        team.add(num[now])
                    }
                }
            }
        }
    }

    return n - cnt
}

 

나의 풀이 - 2차

 형식은 대강 비슷하다. 다만 이번에는 DFS를 이용해서 시간 복잡도를 O(N)까지 줄였다.

fun main() = with(System.`in`.bufferedReader()) {
    val t = readLine().toInt()
    val test = mutableListOf<Pair<Int, IntArray>>()

    repeat(t) {
        val n = readLine().toInt()
        val temp = IntArray(n + 1)
        readLine().split(" ").map { it.toInt() }.forEachIndexed { i, v -> temp[i + 1] = v }
        test.add(n to temp)
     }

    test.forEach {
        val visited = BooleanArray(it.first + 1) { false }
        val student = BooleanArray(it.first + 1) { false }
        var count = 0

        for (i in 1..it.first) {
            if (!visited[i]) {
                count += dfs(i, it.second, visited, student)
            }
        }
        println(it.first - count)
    }

}

fun dfs(start: Int, num: IntArray, visited: BooleanArray, student: BooleanArray): Int {
    var cnt = 0
    visited[start] = true

    val next = num[start]
    var count = 0
    if (!visited[next]) {
        count += dfs(next, num, visited, student)
    } else if (!student[next]) {
        count++
        var i = next
        while (i != start) {
            count++
            i = num[i]
        }
    }

    student[start] = true

    return count
}