ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Algorithm) BOJ) 백준 9466 - 텀프로젝트
    Algorithm/BOJ 2019. 6. 4. 17:30
    728x90

     

    문제보러가기

    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()
    

     

    댓글

Designed by Tistory.