1. 문제 링크 및 문제
https://www.acmicpc.net/problem/9466
2. 해결 방법 생각해보자 ...
1. 그래프 탐색으로 팀인 지 확인 후, 전체 학생 수 - 팀인 학생 수
2. 팀인 지 확인하는 방법
팀이 만들어지는 경우 (= 싸이클이 형성된 경우)
- 자기 자신 선택한 경우 ( 혼자 팀 가능 )
- 선택한 팀원들끼리 싸이클이 형성될 때, 팀 생성
팀이 안만들어지는 경우 (= 싸이클이 없는 경우)
- 자신이 선택한 학생이, 다른 학생을 선택하였고, 그 다른 학생들도 자신을 선택하지 않은 경우
3. 싸이클 확인하는 방법
i번째 학생이 i번으로 나오면 됨.
i로 나오면 answer += 1 == 싸이클이 한 번 확인 되었다
그렇다면, 한 번 확인된 싸이클은 다시 확인할 필요가 없음!
예) 1번 학생 -> 2번학생 선택, 2번 -> 3번 선택, 3번 -> 1번 선택
그럼 1->2->3->1 로 1번 학생이 1번으로 나오게 된다.
즉, 싸이클이 형성된 것이다.
i번째 학생이 방문한 곳 visited 로 표시
i번째 학생 싸이클 확인이 끝나면 finished 로 표시
DFS(1)
그렇다면 1번학생일 때 (현재 1 )
- visited[1] = true;
- DFS(1번 학생이 선택한 학생) = DFS(2)
2번 학생일 때 ( 현재 1 -> 2 )
- visited[2] = true
- DFS(2번 학생이 선택한 학생 ) = DFS(3)
3번학생일 때 ( 현재 1 -> 2 -> 3 )
- visited[3] = true
- DFS(3번 학생이 선택한 학생 ) = DFS(1)
1번 학생일 때 ( 현재 1 -> 2 -> 3 -> 1 )
- 이미 visited[1] = true !!
- 싸이클이 형성된 경우이므로, answer += 1
- finished[1] = true
현재 상태 : visited[True, True, True]
Finished[True,False,False]
DFS(2)
2번 학생일 때
- 이미 visited[2] = true !!
- finished[2] = false 이므로, 검사가 끝나기 전 싸이클이 형성된 경우!
answer += 1
finished[2] = true
현재 상태 : visited[True, True, True]
Finished[True,True,False]
즉 정리해보자면
- 검사가 끝나지 않았을 때
◦ 처음 방문한다면, DFS(선택한 학생) 실행
◦ 재방문 이라면, 싸이클 형성됨 !
- 이미 전에 검색한 적이 있다면
◦ 확인할 필요 X, return
코드로 표현해보자면,
- (finished[i] == false) 이면서
◦ visited[i] == false ?
DFS
◦ visited[i] == true ?
ans += 1
finished[i] = true
- finished[i] == true 일 땐
◦ 확인할 필요 X, return
시간복잡도
N의 범위가 100,000 이므로,
최대값인 경우 10만번 싸이클 확인을 하면
O(n^2)의 시간복잡도를 갖게 되고, 최대 10만의 n 값으로 탐색한다면 시간 초과가 남.
따라서 finished 로 이미 검사한 싸이클은 넘어가주면서 O(N)의 시간 복잡도로 탐색
3. 코드
import java.util.*;
import java.io.*;
public class Main{
static int N; // 전체 학생 수
static int ans = 0; // 형성된 팀들의 학생 수
static int[] arr; // i번째 학생이 선택한 학생 배열
static boolean[] visited; // 방문 확인
static boolean[] finished; // DFS 검사 끝 확인
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TestCase = Integer.parseInt(br.readLine());
for(int t=0;t<TestCase;t++){
// 값 입력 -->
N = Integer.parseInt(br.readLine());
arr = new int[N+1];
finished = new boolean[N+1];
visited = new boolean[N+1];
ans = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1;i<N+1;i++)arr[i] = Integer.parseInt(st.nextToken());
// <--
// 각 학생마다 싸이클 확인
for(int i=1;i<N+1;i++){
DFS(i);
}
System.out.println(N-ans);
}
}
public static void DFS(int x){
if(finished[x]) return; // DFS 탐색을 했었던 경우 return
if(visited[x]){// DFS 탐색이 끝나기 전, visited[x] = true 라면 재방문인 경우이므로 ans += 1;
finished[x] = true;
ans ++;
}
visited[x] = true;
DFS(arr[x]);
finished[x] = true;
}
}실수
처음에 부모가 같으면 되는 문제인 줄 알고 유니온 파인드로 접근했는데
유니온 파인드는 부모를 합쳐주는 문제이므로
답과 완저니 멀어지는 방식이었당.
그래서 그래프 탐색을 생각했는데
시간 초과 오류를 위해 이미 방문한 부분을 어떻게 표시하지? 했는데
finished 라는 새로운 변수를 만들어,
탐색이 끝났을 때 true 로 만들어주면 되는 아쥬 간단한 방법이 있었다.
풀이를 참고해서 풀었지만, 점점 문제의 정답에 가까운 코드를 작성하고 있다! 오옝 ~
