[Algorithm/BOJ] 9466 - 텀 프로젝트 Swift

문제 풀이: 

텀 프로젝트를 위한 팀을 만들면서 원하는 팀원을 각자 고른다.

여기서 중요한건 DFS를 이용해서 Cycle을 확인해야 하는 것이다.

 

위 표에서 4 -> 7 -> 6 -> 4와 같은 Cycle을 확인할 수 있고 4, 6, 7은 같은 팀이 된다.

3번은 자기 자신을 선택했으므로 1번과 5번은 3번을 선택했지만 팀을 이룰 수 없고 3번 혼자 팀이 된다. 

그리고 전체 인원에서 팀이 된 모든 번호의 개수를 제외하면 팀을 이루지 못한 인원의 수가 나와 답이 된다.

 

코드: 

func dfs(
    _ num: Int,
    _ nums: [Int],
    _ check: inout [Bool],
    _ team: inout [Int],
    _ teams: inout [[Int]]
) {
    check[num] = true
    team.append(num)
    // 선택한 학생의 번호
    let s = nums[num]
    
    // 선택한 학생이 팀이 없을 때
    if check[s] == false { 
        dfs(s, nums, &check, &team, &teams)
    } else {
    	// 선택한 학생의 번호가 team에 포함되어 있다면 cycle 형성되므로 팀을 이룸
        if team.contains(s) {
            teams.append(Array(team[team.firstIndex(of: s)!...]))
        }
        return
    }
}

for _ in 0 ..< Int(readLine()!)! {
    let n = Int(readLine()!)!
    let nums = [0] + readLine()!.split(separator: " ")
        .map { Int(String($0))! }
    var check = [Bool](repeating: false, count: n+1)
    var teams = [[Int]]()

    for i in 0 ..< n+1 {
        if check[i] == false {
            var team = [Int]()
            dfs(i, nums, &check, &team, &teams)
        }
    }
    print(n + 1 - teams.flatMap({ $0 }).count)
}

 

문제: 

9466번: 텀 프로젝트