백준 9466번: 텀 프로젝트 (Kotlin)

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

9466번: 텀 프로젝트

 

풀이

문제를 이해하기 위해 예제를 그림으로 그려보았다.

 

어디서 시작해도 사이클이 생긴다

 

팀을 이루기 위해선 각 학생들이 선택한 학생들을 따라갔을 때, 사이클이 형성되어야 한다는 걸 알 수 있다. 그리고 사이클은 어디서 시작하든지 반드시 생긴다. 사이클이 생기지 않으려면 중간에 화살표가 끊기거나 화살표가 무한히 이어져야 하는데, 그럴려면 팀원을 선택하지 않은 학생이 있거나 학생 수가 무한히 많아야 하기 때문이다.

 

또한, 2 -> 1 -> 3 -> 3 처럼 중간에 다른 사이클이 생기는 학생이 팀에 속하지 않는 학생이 된다.

 

그래서 나는 각 학생이 선택한 학생을 배열에 저장한 후, dfs를 사용해서 사이클을 만드는 학생들의 수를 구했다. 그리고 전체 학생 수에서 빼주는 방식으로 답을 구했다.

 

구현 방식

(1) 모든 학생을 한번씩 시작점으로 탐색해서, 자기 자신으로 돌아오는지 확인

가장 간단해 보이는 건 모든 학생을 시작 지점으로 탐색해서 자기 자신으로 돌아오는지 확인하는 방법인데, 이렇게 하면 시간 초과가 발생한다. 탐색에 걸리는 시간은 O(n), 모든 학생마다 탐색하면 O(n^2) = 100억이 되기 때문이다.

 

그래서 그래프 탐색에서 시간을 줄이는 방법인, 한번 확인한 학생은 다시 확인하지 않도록 해야 문제를 해결할 수 있다. 

한번 방문했던 학생이 다시 나오면, 이전의 탐색 과정이 그대로 등장한다는 점을 이용한다.

(ex) 1 -> 2  -> 3 -> 1 을 탐색하고 나서, 4 -> 1이 나온다면 1 -> 2 -> 3 -> 1 탐색을 다시 반복하게 된다.)

 

(2) 중복 체크 자료구조 2개 사용 

확인한 학생은 다시 방문하지 않도록 해야 하는데, 문제는 사이클을 이루는 학생이 다시 나타났을 때 방금 탐색하다가 확인한 건지, 이전 탐색에서 확인한 건지 알 수가 없다는 것이다.

 

그래서 방문 체크하는 배열을 2개 사용하였다. 

- finished: 사이클을 형성 여부까지 확인했는지 체크

- visited: 한 번이라도 방문 했는지 체크

 

알고리즘) dfs (재귀 or 스택)

1. 처음 방문하는 학생일 경우 visited에 체크하고 그 학생이 선택한 학생을 방문한다.
2. 다시 방문하는 학생일 경우,
   1. finished가 체크된 학생 -> 이전의 탐색 과정이 그대로 나오므로 탐색을 종료한다.
   2. 그렇지 않다면, 사이클을 형성하는 학생이므로, 그 학생의 다음 학생부터 자기 자신으로 되돌아올 때까지 반복문을 돌리면서 사이클을 형성하는 학생 카운트를 증가시킨다.
3. 함수나 스택을 빠져나가면서 사이클까지 모두 확인했음을 finished에 체크한다.

 

(3) 방문 확인 배열 + 탐색을 시작할 때마다 새로운 중복 체크 자료구조를 생성해서 사용

새 탐색을 시작할 때마다 추가 자료구조 사용

탐색 과정에서 이전에 사이클 여부까지 확인했는지를 필터링할 수는 있지만, 새로운 자료구조를 생성할 때마다 O(n)의 시간복잡도가 더 필요해서 결국 O(n^2)으로 시간 초과가 발생한다.

 

나는 여기서 많이 해맸었다..ㅋㅋ

 

코드1 (방식 2)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var graph: IntArray
lateinit var visited: BooleanArray
lateinit var finished: BooleanArray
var count = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t){
        val n = readLine().toInt()
        val st = StringTokenizer(readLine())
        count = 0
        graph = IntArray(n+1)
        visited = BooleanArray(n+1)
        finished = BooleanArray(n+1)

        for (i in 1..n){
            graph[i] = st.nextToken().toInt()
        }

        for (i in 1..n){
            if (visited[i].not()) dfs(i)
        }

        answer.append(n - count).appendLine()
    }

    print(answer)
}

fun dfs(student: Int){
    // 처음 방문한 학생
    if (visited[student].not()) {
        visited[student] = true // 방문 체크
        dfs(graph[student])     // 다음 학생 방문
    }
    else{
        if (finished[student]) return // 사이클 형성 여부까지 이미 확인한 학생
        else{
            var nextStudent = graph[student] // 자신부터 시작하면 while문이 안돌아간다

            while (nextStudent != student){
                count++ // 사이클을 형성하는 학생 수 증가
                nextStudent = graph[nextStudent]
            }
            count++ // 자기 자신도 센다 ex) 2 -> 1 -> 3 -> 2: 반복문에서 1,3을 세고 마지막에 2를 센다

            return
        }
    }

    finished[student] = true // 사이클 형성 여부까지 확인했음
}

 

코드2 (방식2와 개념은 같지만 추가 방문 체크용 자료 구조로 Map을 사용했습니다)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var graph: IntArray
lateinit var visited: BooleanArray
lateinit var finished: BooleanArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t){
        val n = readLine().toInt()
        val st = StringTokenizer(readLine())
        var count = 0
        graph = IntArray(n+1)
        visited = BooleanArray(n+1)
        finished = BooleanArray(n+1)

        for (i in 1..n){
            graph[i] = st.nextToken().toInt()
        }

        for (i in 1..n){
            if (!visited[i]){
                count += dfs(i, mutableListOf(), HashMap<Int, Int>())
                // updateGroup(hasGroup, students, startIndex)
            }
        }

        answer.append(n - count).appendLine()
    }

    print(answer)
}

// Map을 추가 방문 체크 자료구조로 사용했습니다
fun dfs(student: Int, studentList: MutableList<Int>, indexMap: MutableMap<Int, Int>): Int {
    if (finished[student]) return 0 // 사이클 형성 여부가 이미 확인된 학생
    if (visited[student]) {         // 사이클이 형성됨
        return studentList.size - indexMap[student]!!
    }

    visited[student] = true
    indexMap[student] = studentList.size
    studentList.add(student)
    val count = dfs(graph[student], studentList, indexMap)

    finished[student] = true
    return count
}