[백준] Swift 9466 텀 프로젝트 DFS

문제 :

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

9466번: 텀 프로젝트

분석 :

학생들이 cycle을 이루는지 파악하기 위해 DFS로 접근해야 한다. 처음에 접근한 방식은 while문을 통해 dfs 탐색을 하고자 했지만 visit를 검사해주지 않아서 시간초과가 났다. 그래서 블로그를 참고해 다시 풀었다 ㅠ

 

일반적으로 방문한 노드인지 확인을 위해 visit배열을 사용하는데 

여기서는 done(팀을 이루었는지 아닌지)도 배열을 하나 새로 만든다. 같이 프로젝트 하고 싶은 친구가 겹칠 수 있기 때문에(ex> arr[1] : 3, arr[3] : 3, arr[5] = 3) visit가 true일때 done 배열을 통해 이미 팀 매칭이 끝났는지 아닌지 확인해야 한다. 

간단하게 생각했는데 생각보다 재귀에 done 배열까지 있어 추상적이고 어렵게 느껴졌다 .. 

 

시간초과난 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/17.
//

import Foundation
var Tcase = Int(readLine()!)!

func dfs(_ arr:[Int]) -> Int {
    var answer = 0
    for (idx, i) in arr.enumerated() { // me, friend
        var cnt = 0
        let start = idx + 1
        var friend = i
        while(start != friend) {
            if( friend == arr[friend-1]) {
                break
            }else {
                friend = arr[friend-1]
                //cnt += 1
            }
        }
        if(start == friend){
            cnt += 1
        }else {
            cnt = 0
        }
        answer += cnt
    }
    return arr.count - answer
}

for _ in 0..<Tcase {
    var n = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ Int($0)!}
    print(dfs(arr))
}

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/17.
//

import Foundation
var Tcase = Int(readLine()!)!
var visit: [Bool] = []
var done: [Bool] = [] //cycle을 거친 node인지(팀 매칭을 거친 노드인지)
var cnt = 0

func dfs(_ arr:[Int], cur: Int) {
    var nextNode = arr[cur]
    visit[cur] = true
    if !visit[nextNode] {
        dfs(arr, cur: nextNode)
    }else {
        if !done[nextNode] { // cycle이 되었는데 아직 팀 매칭 되지 않았다면
            while nextNode != cur { // cycle 친구들 저장
                cnt += 1
                nextNode = arr[nextNode]
            }
            cnt += 1 // cur 자기 카운드
        }
    }
    done[cur] = true
}

for _ in 0..<Tcase {
    let n = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ Int($0)!}
    arr.insert(0, at: 0) //의미 없는 수 index 1부터 ~ 계산하기 위해 
    cnt = 0
    visit = Array(repeating: false, count: n+1)
    done = Array(repeating: false, count: n+1)
    for i in arr {
        if !visit[i] {
            dfs(arr, cur: i)
        }
    }
    print(arr.count - cnt)
    
}