[ 백준 9466 ] - 텀 프로젝트 (Kotlin)

 

 

9466번: 텀 프로젝트

 

문제 이해 & 기본 개념

• n 명의 학생이 각각 같이 팀이 되고 싶은 학생을 1명씩 선택한다.
• 학생들을(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
• 학생들이 선택한 결과가 주어질 때, 팀에 속하지 않는 학생의 수를 구하는 문제

---

중요 포인트

• 선택한 학생들끼리 사이클을 이루는 경우가 팀이 되는 것
• 선택한 학생을 계속 타고 이동하면서 사이클이 이루어지는지를 체크하면 된다.
• 사이클이 생기는 경우(팀이 되는 경우)는 여러가지가 있다.
  
  1. 1->2->3->1 처럼 첫 학생이 사이클의 시작점이 되는 경우
  2. 1->2->3->4->5->3 처럼 중간에서 사이클이 생기는 경우
• 이 두 가지 경우를 유의하여 풀어야 한다.

---

최종 풀이

• 각 노드(학생)에 대해 dfs를 수행한다.
• 현재 학생이 선택한 학생을 따라 dfs를 진행하며, 이전 노드들을 기록한다.
• 만약, 이전에 방문했던 노드를 재방문하게 된다면 사이클이 생긴 것이다.
• 1->2->3->4->5->3 처럼 방문했을 때, 3에서 사이클이 시작 되었기 때문에, 마지막 3에서 재방문이 된다.
• 사이클의 시작점(3)까지 돌아가면서 그 과정에 있는 번호를 팀으로 추가한다.

* 사이클이 발생한 순간 자기 자신을 리턴 (자신이 사이클의 시작이기 때문)
* 리턴 값이 자신과 같으면 사이클에 포함된 팀원이 다 추가된 것
* 리턴 값이 자신과 다르고 -1이 아니라면 team에 자신을 추가
* 리턴 값이 -1이라는 것은 이제 더이상 팀 구성이 불가능하다는 뜻

---

 

주의 할 점

• n이 최대 100,000까지이므로, n에 대해 각각 dfs를 실행하면 최악의 경우 O(n^2)이 될 수 있다.
  • 최악의 경우는 1->2->3->4->...->n, 2->3->4->...->n 처럼 모든 경우를 다 체크하는 경우
• 시간을 줄일 수 있는 방법을 생각해야 한다.

1. 이미 팀이 만들어진 경우

• 사이클이 발생하여 팀이 된 학생들은 HashSet에다가 담아 관리한다.
• 이후 탐색하는 과정에서 이미 팀이 된 학생을 만나면 바로 return 한다.

   // 이미 팀에 포함된 경우
    if(team.contains(cur)) return -1

2. 팀을 만들 수 없는 경우

• 한 번 방문 했는데, 팀이 되지 않았다면 (사이클이 생기지 않았다면) 그 이후에도 팀을 만들 수 없다.
  • 1->2->3->4->5->3 의 경우 1번, 2번은 방문 했지만 팀이 되지 못했다.
  • 만약, 이후에 10->1과 같은 경우가 나오면 1은 어차피 팀이 되지 못하는 학생이므로 더 이상 진행할 필요가 없다.
• 이 경우를 체크하기 위해 visited 배열을 만들어 방문 체크를 해줘야한다.

    // 이미 방문한 경우 (이전 방문에서 팀에 포함되지 않았다면, 팀 구성 불가)
    if(visited[cur]) return -1

---

소스 코드

package Gold.BOJ9466

import java.util.*
import kotlin.collections.HashSet

lateinit var team:HashSet<Int>
lateinit var nodes:Array<Int>
lateinit var visited:Array<Boolean>

/**
 * 사이클이 발생한 순간 자기 자신을 리턴 (자신이 사이클의 시작이기 때문)
 * 리턴 값이 자신과 같으면 사이클에 포함된 팀원이 다 추가된 것
 * 리턴 값이 자신과 다르고 -1이 아니라면 team에 자신을 추가
 * 리턴 값이 -1이라는 것은 이제 더이상 팀 구성이 불가능하다는 뜻
 */
fun dfs(cur:Int, prev:HashSet<Int>): Int {
    // 이미 팀에 포함된 경우
    if(team.contains(cur)) return -1
    // 이미 방문(현재 dfs에서)한 경우 (사이클 발생 == 팀 구성 가능)
    if(prev.contains(cur)){
        team.add(cur)
        return cur
    }
    // 이미 방문(다른 dfs에서)한 경우 (이전 방문에서 팀에 포함되지 않았다면, 팀 구성 불가)
    if(visited[cur]) return -1
    
    visited[cur] = true
    prev.add(cur)

    val cycle = dfs(nodes[cur], prev)
    if(cycle == cur) return -1
    else if(cycle != -1) team.add(cur)

    return cycle
}

fun solve():Int {
    /**
     * 이미 팀이 만들어진 경우
     * 팀을 만들 수 없는 경우 = (이전 방문을 통해 팀을 만들 수 없는 것이 확정된 경우)
     * 
     * 이 2가지를 모두 체크해줘야 시간 초과 나지 않음
     */
    for (i in nodes.indices){
        if(team.contains(i)) continue
        dfs(i, hashSetOf())
    }
    return nodes.size - team.size
}

fun main(){
    val t = readln().toInt()
    val sj = StringJoiner("\n")

    repeat(t){
        nodes = Array(readln().toInt()){0}
        visited = Array(nodes.size){false}
        team = hashSetOf()
        StringTokenizer(readln()).apply{
            repeat(countTokens()){
                nodes[it] = nextToken().toInt()-1
            }
        }
        sj.add("${solve()}")
    }
    println(sj)
}

 

---

시간 초과 (2%)

• 아래 코드에선 사이클을 start == cur로 판별하고 있다.
• dfs를 시작한 노드와 cur이 같아지면 사이클로 간주하는 코드
• 즉, 첫 학생이 사이클의 시작이 되는 경우만 고려한 코드여서 시간 초과가 났다.
  • 1->2->3->4->5->3인 경우
    • 1->2->3->4->5->3
    • 2->3->4->5->3
    • 3->4->5->3  ==> 이때 사이클이 확인 됨
  • 이렇게 결국 모든 노드에 대해 dfs를 수행하므로 시간 초과 발생

import java.util.*
import kotlin.collections.HashSet

lateinit var team:HashSet<Int>
lateinit var nodes:Array<Int>

fun dfs(start:Int, cur:Int, prev:HashSet<Int>): Boolean{
    if(prev.isNotEmpty() && start == cur) return true // 팀 완료
    if(prev.contains(cur)) return false // 더 이상 진행 불가

    prev.add(cur)
    val isBuild = dfs(start, nodes[cur], prev)
    if(isBuild) team.add(cur) // 팀 해시에 추가

    return false
}

fun solve():Int {
    /**
     * 이미 팀이 된 사람들은 HashSet에 담아두기
     * 이미 팀이 됐으면 dfs 패스
     */
    for (i in nodes.indices){
        dfs(i, i, hashSetOf())
    }
    return nodes.size - team.size
}

fun main(){
    val t = readln().toInt()

    repeat(t){
        nodes = Array(readln().toInt()){0}
        team = hashSetOf()
        StringTokenizer(readln()).apply{
            repeat(countTokens()){
                nodes[it] = nextToken().toInt()-1
            }
        }
        println(solve())
    }
}

---

시간 초과 (80%)

• 위의 케이스를 해결한 코드
• 중간에 사이클이 발생하는 경우를 체크하여, 이미 팀이 이루어진 경우는 재방문하지 않도록 하였다.
• 위에서도 말했듯이, 팀을 이룰 수 없는 경우를 체크하지 않아서 최악의 경우 시간 초과 발생

import java.util.*
import kotlin.collections.HashSet

lateinit var team:HashSet<Int>
lateinit var nodes:Array<Int>

fun dfs2(cur:Int, prev:HashSet<Int>): Int {
    if(team.contains(cur)) return -1
    if(prev.contains(cur)){
        team.add(cur)
        return cur
    }
    prev.add(cur)

    val cycle = dfs2(nodes[cur], prev)
    if(cycle == cur) return -1
    else if(cycle != -1) team.add(cur)

    return cycle
}

fun solve():Int {
    for (i in nodes.indices){
        if(team.contains(i)) continue
        dfs2(i, hashSetOf())
    }
    return nodes.size - team.size
}

fun main(){
    val t = readln().toInt()
    val sj = StringJoiner("\n")

    repeat(t){
        nodes = Array(readln().toInt()){0}
        team = hashSetOf()
        StringTokenizer(readln()).apply{
            repeat(countTokens()){
                nodes[it] = nextToken().toInt()-1
            }
        }
        sj.add("${solve()}")
    }
    println(sj)
}