[백준] 27. 텀 프로젝트 9466 해설

텀 프로젝트

9466번: 텀 프로젝트

 

문제

 

풀이

문제를 해결하는 아이디어 자체는 꽤 간단합니다.

먼저 팀이 만들어지는 경우는 원하는 학생들끼리의 사이클이 형성되는 경우 밖에 없습니다

(본인을 선택하는 경우도 사이클이 형성된다.)

팀이 되는 경우

 

반대로 팀이 되지 않는 경우는 사이클이 형성되지 않는 경우입니다.

팀이 안 되는 경우

 

생각보다 규칙이 간단하기 때문에 구현만 잘 진행해 주면 됩니다.

 

원하는 학생을 끝까지 탐색해줘야 하기 때문에 깊이 우선 탐색으로 구현해 주면 됩니다.

DFS를 진행해 주면서 아래 두 가지 경우만 처리해 주면 됩니다.

• 사이클이 형성되지 않는 경우 -> 팀 X
• 사이클이 형성되는 경우 -> 팀 O

 

하지만 학생의 수가 최대 100,000으로 일반적인 DFS로는 시간 초과가 발생합니다. 

따라서 한 번 거쳐간 사람은 다시 탐색하지 않도록 O(n)의 시간 복잡도로 DFS를 구현해 주면 됩니다.

 

 

최악의 경우

 

위의 예시가 일반적인 DFS로 구현할 시 시간초과가 발생할 수 있는 최악의 경우입니다.

1번 사람은 n번

2번 사람은 n-1번

3번 사람은 n-2번

..

n번 사람은 1번

을 탐색하기 때문에 O(n^2)의 시간 복잡도가 발생하게 됩니다.

 

하지만 실질적으로 1번 사람을 탐색할 때 모든 인원을 거쳐가기 때문에 2번부터는 탐색을 하지 않아도 됩니다.

 

 

예시

위 예시에서는 1번 사람을 탐색할 때 4, 5, 6, 7, 8, 9번 사람을 거쳐가며

7, 8, 9 번은 사이클이 형성되어 팀이 되고

1, 4, 5, 6 번은 사이클이 형성되지 않아 팀이 되지 않습니다.

 

그다음 2번 사람을 탐색할 때 3번 사람을 거쳐가며

3번 사람은 사이클이 형성되어 팀이 되고

2번 사람은 사이클이 형성되지 않아 팀이 되지 않습니다.

이후 탐색이 종료됩니다.

 

 

구현 방법은 다음과 같습니다.

1. dfs를 돌면서 거쳐간 인원에 대해 방문처리를 해줍니다.
2. 이미 방문했던 사람을 다시 방문하는 경우는 사이클이 생기는 경우이기 때문에 팀으로 처리해 줍니다.
3. 그 이외의 경우는 팀이 아닌 것으로 간주하고 중복 탐색이 발생하지 않도록 처리해 줍니다.

 

이를 구현하기 위해 중복 탐색을 방지하는 finish 배열과 현재 dfs 내부 방문여부인 visited 배열을 사용해주었습니다.

아마 코드를 보시는 것이 더 쉽게 이해가 되실 겁니다.

 

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    
    val sb = StringBuilder()
    repeat(input()) {

        val N = input()
        val arr = IntArray(N+1)
        val finish = BooleanArray(N+1)  // 이미 탐색이 끝난 사람
        val visited = BooleanArray(N+1) // 현재 dfs의 방문여부, dfs가 끝나면 finish처리

        repeat(N) { i ->
            arr[i+1] = input()
        }

        var result = N
        fun dfs(num: Int) {
            // 이미 탐색이 끝난 사람인 경우
            if (finish[num]) return

            val next = arr[num]
            // 방문한적은 있지만 탐색이 종료되지 않은 경우
            // 즉 사이클이 생기는 경우
            if (visited[num] && !finish[num]) {
                finish[num] = true
                result--
                var nx = next
                // 사이클 내부 인원 팀처리
                while (num != nx) {
                    finish[nx] = true
                    nx = arr[nx]
                    result--
                }
                return
            }
            // 방문한적도 탐색이 끝나지도 않은 경우
            visited[num] = true
            dfs(next)
            finish[num] = true
        }

        for (i in 1..N) {
            // 탐색하지 않는 사람만 dfs 진행
            if (!visited[i] && !finish[i])
                dfs(i)
        }
        sb.appendLine(result)
    }
    print(sb)
}