[백준/BOJ] 9466번: 텀 프로젝트

문제

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

9466번: 텀 프로젝트

해설

우선 배열의 인덱스는 0부터 시작이므로 각 학생을 0번부터 시작하도록 -1을 해준다.

예시 입력1의 첫번째 테스트 케이스는 다음과 같이 된다.

학생들은 서로 원하는 경우에만 팀이 될 수 있다.

즉, 사이클이 형성되야만 팀이 될 수 있다는 것이다.

 

우선 필요한 변수들을 생각해보자.

이미 방문했던 칸은 재방문할 필요가 없으므로 방문 여부를 처리해줄 visited 배열을 선언한다.

또한 사이클이 형성되었는지를 처리해줄 isCycle 배열을 선언해준다.

팀이 되길 원하는 사람을 저장해둔 변수를 wantTeam이라고 하자.

 

우선 for문을 통해 0번부터 원하는 사람과 팀이 될 수 있는지 알아보자.

for(i in 0 until n) {
    if(!visited[i]) linkTeam(i)
}

0번에서 시작하므로 visited[0] = true로 처리해준다.

0번은 2번과 팀이 되길 원한다. 2번은 아직 방문하지 않았었으므로 재귀를 통해 2번이 원하는 사람을 보자.

 

재귀를 통해 2번부터 시작하는 것이므로, 2번의 방문 여부를 처리해준다.

2번은 2번과 팀이 되길 원한다. 또한 2번은 이미 방문했던 칸이므로, 사이클 검사를 해주자.

사이클을 검사하는 방법은 간단하다.

왔던 길을 되돌아가면 된다.

 

예를 들어, (3, 6), (6, 5), (5, 3)을 보자.

사이클 검사 전, 3번에서 시작하여 5번까지 연결이 된다.

즉, 재귀를 통해 5번이 시작 노드로 되어 있고, 3번과 팀을 하고자 하고,

3번은 6번과, 6번은 5번과 팀을 하길 원한다. 결론적으로 사이클을 이루는 것을 확인할 수 있다.

설명만으로는 이해하기 힘들 것 같으므로 코드를 보면 좀 더 쉬운 이해를 할 수 있을 것이다.

if(!isCycle[nextHuman]) {
    while(nextHuman != human) {
        nextHuman = wantTeam[nextHuman]
        cnt++
    }
    cnt++
}

cnt는 팀을 이루고 있는 인원을 뜻한다. 반복문을 탈출 후 한 번 더 증가시켜주는 것은 자기 자신도 포함해야 하기 때문이다.

 

모든 반복이 끝났다면, 팀을 이루고 있는 인원을 구하게 된다.

문제에서 요구하는 것은 팀을 이루지 못한 사람이므로 n - cnt를 출력하면 된다.

코드

private lateinit var visited: BooleanArray
private lateinit var isCycle: BooleanArray
private lateinit var wantTeam: IntArray
private var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    repeat(readLine().toInt()) {
        val n = readLine().toInt()
        visited = BooleanArray(n)
        isCycle = BooleanArray(n)

        wantTeam = readLine().split(" ").map { it.toInt() - 1 }.toIntArray()

        for(i in 0 until n) {
            if(!visited[i]) linkTeam(i)
        }

        println(n - cnt)
        cnt = 0
    }
}

private fun linkTeam(human: Int) {
    visited[human] = true
    var nextHuman = wantTeam[human]

    if(!visited[nextHuman]) linkTeam(nextHuman)
    else if(!isCycle[nextHuman]) {
        while(nextHuman != human) {
            nextHuman = wantTeam[nextHuman]
            cnt++
        }
        cnt++
    }
    isCycle[human] = true
}