백준 2668 숫자고르기

출처: https://www.acmicpc.net/problem/2668

분류: 그래프, dfs

---

접근방식

1~n 까지에 각각 숫자가 매겨져 있을 때,
매겨진 숫자와 자신의 숫자의 집합이 같아지도록 최대한 많이 뽑아내는 문제입니다.

1~n을 노드 자신의 인덱스로, 매겨진 숫자를 다음 노드를 가리키는 그래프로 생각해보면,
결국 자기 자신으로 돌아오는 사이클이 아니면 절대 같은 집합이 될 수 없다는 걸 알 수 있습니다.

이렇게 각 사이클들을 더해주면 끝입니다 :)

전체 defaultVisit과 방문하면서 체크할 visit 배열을 만들어두고 탐색해서 
사이클이 생겼다면 해당 visit을 defaultVisit으로 업데이트 시켜주는 방식으로 구현했습니다.

for i in 0..<n {
    visit = defaultVisit
    visit[i] = true
    let nodesInCycle = hasCycle(current: graph[i], from: i, count: 1)
    if nodesInCycle > 0 {
        defaultVisit = visit
    }
}

 

해결방법

let n = Int(readLine()!)!
var graph = [Int](repeating: 0, count: n)
for i in 0..<n {
    let dest = Int(readLine()!)! - 1
    graph[i] = dest
}

var defaultVisit = (0..<n).map { _ in false }
var visit = defaultVisit

func hasCycle(current idx: Int, from start: Int, count: Int) -> Int {
    guard idx != start else { return count }
    guard !visit[idx] else { return 0 }
    visit[idx] = true
    return hasCycle(current: graph[idx], from: start, count: count+1)
}

for i in 0..<n {
    visit = defaultVisit
    visit[i] = true
    let nodesInCycle = hasCycle(current: graph[i], from: i, count: 1)
    if nodesInCycle > 0 {
        defaultVisit = visit
    }
}

var result = [Int]()
for i in 0..<n {
    if defaultVisit[i] {
        result.append(i+1)
    }
}
print(result.count)
result.forEach { print($0) }

 

배운점