Algorithm) BOJ) 백준 9466 - 텀프로젝트

 

문제보러가기

1. 초기접근

문제 조건 해석

사이클을이 되면 팀을 이룬다는 것을 알 수 있다.

DFS로 생각할 수 있지만, 난 한 명만 찍을 수 있지만 다수의 사람이 날 찍을 수 있다. 단순한 방문체크로는 한계가 있다.

알고리즘

탐색이 끝났는데, 팀을 이루지 못하면 팀을 이룰 수 없다.

—> 1차 방문체크(visited)와 탐색이 끝난 완전 방문체크(finished) 2번 체크해야 한다.

—> 탐색 중에 완전 finished가 아닌 visitied를 만났다면 싸이클을 찾은 것이라고 할 수 있다.

그 순간부터 count를 세면서 다시 자신으로 돌아오면 한 팀을 다 돈 것이다. (사이클 찾은 후 시작이므로 무조건 자신에게 돌아온다.)

전체 사람 수 에서 count를 빼면 정답.

 

2. 회고

c++ 로 전에 한번 풀었던 문제지만.. 그때 제대로 이해를 못하고 넘어갔던 것 같다.

이해가 안되서 무척이나 애먹었던 문제…

2번 방문체크까지는 알겠는데 싸이클을 찾은 후 부터 다시 돌아간다는 말이 이해가 되지 않았다.

싸이클을 찾았으니 찾은 순간부터 다시 시작해 돌면 다시 자신이 나온다는 이 개념을 이해하는데 많은 시간을 썼다.

 

3. 코드

func solution() {
    for _ in 0...readLine().map({Int($0) ?? 0})! {
        guard let n = readLine().map({Int($0)!}) else { return }
        var graph = [Int](repeating: 0, count: n+1)
        var visited = [Bool](repeating: false, count: n+1)
        var finished = [Bool](repeating: false, count: n+1)
        var cnt = 0
        var startOfCycle = 0
        
        guard let num = readLine()?.split(separator: " ").map({Int($0)!}) else { return }
        
        for i in 1...n {
            graph[i] = num[i-1]
        }
        
        func dfs(next current: Int) {
            if finished[current] {
              // 탐색이 끝났으면 탐색하지 않음
               return
            }
            
            if visited[current] {
                // 싸이클 찾음
                cnt += 1
                startOfCycle = current
                var next = graph[current]
                
                while startOfCycle != next {
                    next = graph[next]
                    cnt += 1
                }
                
                
            } else {
                visited[current] = true
                dfs(next: graph[current])
            }
            
            finished[current] = true
        }
        
        for i in 1...n {
            if !visited[i] {
                dfs(next: i)
            }
        }
        
        print(n-cnt)
        
    }
}

solution()