이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다. 위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.
[입력 조건]
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)
[출력 조건]
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
실패한 방법
BFS를 이용한 풀이
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main(){
val br = BufferedReader(InputStreamReader(System.`in`))
val tc = br.readLine().toInt()
repeat(tc){
val n = br.readLine().toInt()
val students = IntArray(n + 1)
br.readLine().split(" ").map{ it.toInt() }.forEachIndexed { index, value ->
students[index + 1] = value // 인덱스 + 1 = 학생 번호
}
println(makeTeam(n, students))
}
}
fun makeTeam(n: Int, students : IntArray): Int {
var count = 0
val selected = BooleanArray(n + 1) // 팀 결성된 친구
for (i in 1..n) {
val visited = BooleanArray(n + 1) // 방문한 친구
if(i == students[i]){ // 나 혼자 팀일 경우
count += 1
selected[i] = true
continue
}
var temp = 1
val q: Queue<Pair<Int, Int>> = LinkedList()
q.add(Pair(i, students[i])) // 현재 노드와 다음 노드
while (q.isNotEmpty()) {
val cur = q.poll()
val next = cur.second
if(visited[next] || selected[next]) { // 방문한, 선택한 노드라면
break
}
if (i == next) { // 다시 돌아 온 경우 -> 팀 결성
count += temp
selected[i] = true // 선택
break
}
q.add(Pair(cur.second, students[cur.second])) // 다음 노드와 다음 다음 노드 넣기
visited[cur.second] = true // 방문처리
temp += 1
}
}
return n - count
}
팀 결성이 끝난 학생을 저장하는 selected 배열과 방문 처리를 위한 visited 배열을 만들었다. 자기 자신을 가리키는 학생과 이미 팀을 결성한 학생을 제외하고 큐에 삽입하였다. 큐에서 나온 학생과 연결되어 있는 학생을 차례로 방문처리를 하다 처음 큐에 넣은 학생의 번호가 나오면 해당 학생을 selected 배열에 저장하고, 총 팀원의 수도 저장하였다. 해당 풀이는 시간초과가 발생하였다. 해당 풀이는 O(N ^2) 시간 복잡도가 도출되고, 입력 받은 N의 최대 갯수가 10^5이라 시간 초과가 발생한다. DFS로 풀리는 문제는 모두 BFS로 풀릴 수 있다고 생각했다.
해결한 방법
import java.io.BufferedReader
import java.io.InputStreamReader
private lateinit var visited : BooleanArray
private lateinit var finished : BooleanArray
private lateinit var students : IntArray
private var n = 0
private var result = 0
fun main(){
val br = BufferedReader(InputStreamReader(System.`in`))
val tc = br.readLine().toInt()
repeat(tc){
n = br.readLine().toInt()
students = IntArray(n + 1)
visited = BooleanArray(n + 1)
finished = BooleanArray(n + 1)
result = 0
br.readLine().split(" ").map{ it.toInt() }.forEachIndexed { index, value ->
students[index + 1] = value // 인덱스 + 1 = 학생 번호
}
// 팀 결성
for(i in 1 .. n){
if(!visited[i]){
makeTeam(i)
}
}
println(n - result)
}
}
fun makeTeam(first : Int) {
visited[first] = true // 현재 방문한 노드 처리
val next = students[first] // 다음에 방문할 노드
if(!visited[next]){ // 다음 노드를 방문하지 않았으면 방문
makeTeam(next)
}
// next를 방문한 적이 있는데, 해당 next가 끝까지 탐색하지 않은 상황 -> cycle
if(visited[next] && !finished[next]){
var temp = next
while (temp != first) {
result += 1 // 연결되어 있는 부분 + 1
temp = students[temp]
}
result += 1 // first도 팀에 포함
}
finished[first] = true
}
DFS를 활용하여 해결하였다. 재귀 함수를 만들고 해당 함수의 파라미터를 학생의 번호로 받는다. 학생 노드의 방문처리를 위한 visited 배열과 학생과 연결되어 있는 노드를 모두 탐색했는지를 확인하는 finshed 배열을 초기화 한다.
재귀 함수에서 파라미터로 전달 받은 학생의 노드를 방문 처리를 하고, 해당 학생과 이어져 있는 학생의 노드의 방문 여부를 체크하고, 방문하지 않았을 경우 방문 처리를 한다.
입력받은 노드와 연결되어 있는 모든 노드를 방문 처리를 하면 (재귀 함수가 종료 되면) finshed 배열에 현재 노드를 저장한다.
만약 이어져 있는 노드의 탐색이 끝나지 않았는데, 방문한 노드를 만나면 팀이 만들어 진 것으로 연결에 속해있는 모든 노드의 수를 더한다.
출력은 팀을 구성하지 못한 학생의 수 이므로 입력받은 총 학생에서 팀이 결성된 학생이 수를 빼어 출력한다.
