-
Algorithm) BOJ) 백준 9466 - 텀프로젝트Algorithm/BOJ 2019. 6. 4. 17:30728x90
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()
'Algorithm > BOJ' 카테고리의 다른 글
Algorithm) BOJ) 백준 7576 - 섬의 개수 (0) 2019.06.06 Algorithm) BOJ) 백준 2667 - 단지번호붙이기 (0) 2019.06.06 Algorithm) BOJ) 백준 1406 - 에디터 (0) 2019.05.21 Algorithm) BOJ) 백준 1676 - 팩토리얼 0의 개수 (0) 2019.05.17 Algorithm) BOJ) 백준 6588 - 골드바흐의 추측 (0) 2019.05.15