출처 : https://www.acmicpc.net/problem/9466
텀 프로젝트 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 9725 | 2401 | 1483 | 23.846% |
문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 3 | 1 | 3 | 7 | 3 | 4 | 6 |
위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
예제 입력 1
2 7 3 1 3 7 3 4 6 8 1 2 3 4 5 6 7 8
예제 출력 1
3 0
출처
ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2013 L번
풀이
문제의 예제를 가시화 해보면 위와 같은 모습을 보입니다.
싸이클을 찾아서 그룹으로 묶고, 싸이클을 이루지 못하는 노드들의 개수를 세서 답으로 도출하는 것입니다.
이 문제에서 시간때문에 고려해야 할 사항은 아래의 예제를 통해 확인할 수 있습니다.
100000
2, 3, 4, 5, 6, ...... , 99998, 99999, 100000, 100000
위의 예제처럼 예시가 나와버리면 탐색한 노드를 바로바로 갱신하지 않으면서 1~100000 까지 순차적으로 탐색할 경우에는 O(N2)이 됩니다.
가령 위의 예제에서 1~7번 노드 순서대로 탐색을 하여 처음에 1->3->3 인 것을 확인하고, 2에서 2->1->3->3 의 과정을 겪으면 시간을 줄이기 어렵습니다.
그래서 1->3->3을 확인하는 과정에서 1은 사이클에 해당하지 않고, 3은 사이클에 해당한다는 것을 판단해야 합니다.
그리고 2->1 로 가는 과정에서 1을 확인하고, 1부터는 탐색을 하지 않아야 합니다.
한 번에 그룹이 아닌 요소들도 체크해야합니다.
위의 예제를 그림으로 확인해보겠습니다.
먼저 1~7까지 순차적으로 탐색하고 이번에 탐색한 노드들
즉, 그룹이 확인된 노드들은 값을 갱신시키고 다음에 확인하여 값이 있으면 건너 뜁니다.
먼저 1번 노드 부터 탐색합니다.
다음은 2번
다음은 3번
다음은 4번을 갱신합니다. 4는 7과 6이 연결되고 다시 자기 자신으로 연결됩니다.
5번째 노드를 보면 싸이클에 포함되지 않기 때문에, -1로 갱신합니다.
6,7은 이미 그룹 2로 정해져서 탐색하지 않습니다.
참고 : 이 문제에서 vector<int> _vector(n) 을 for 루프 안에서 지속적으로 갱신하니 시간 초과가 나왔습니다.
malloc을 큰 사이즈에 대하여 지속적으로 반복하다 보니 그런 문제가 발생한 것 같습니다.
자세한 구현은 소스코드를 참조하시면 될 것 같습니다.
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> #include <vector> using namespace std; #pragma disable(warning:4996) void dfs(vector<int>& _num_vec, vector<int>& _group, int _n) { int group_num = 1; vector<int> is_visited(_n + 1, 0); vector<int> visited_node; for (int n_idx = 1; n_idx <= _n; n_idx++) { // 그룹 번호가 있으면 건너 뛴다. if (_group[n_idx] || is_visited[n_idx]) continue; visited_node.clear(); is_visited[n_idx] = 1; visited_node.push_back(n_idx); int now_node = _num_vec[n_idx]; // 방문하지 않은 노드이면서 그룹도 지정되어있지 않은 경우에만 갱신을 수행 while (is_visited[now_node] == 0 && _group[now_node] == 0) { is_visited[now_node] = 1; visited_node.push_back(now_node); now_node = _num_vec[now_node]; } // 순환 끝나고 시작과 끝이 같으면? int visited_size = visited_node.size(); int vis_idx; // 순환이 시작되는 부분을 찾는다 // 만약 순환이 시작되는 부분이 아니면 -1을 넣어주어 // 그룹을 지을 수 없다는 것을 표시 for (vis_idx = 0; vis_idx < visited_size; vis_idx++) if (visited_node[vis_idx] != now_node) _group[visited_node[vis_idx]] = -1; else break; for (; vis_idx < visited_size; vis_idx++) _group[visited_node[vis_idx]] = group_num; group_num++; } } int main() { ios::sync_with_stdio(false); int T; cin >> T; while (T--) { int n; cin >> n; vector<int> num_vec(n+1,0); vector<int> group(n+1,0); for (int n_idx = 1; n_idx <= n; n_idx++) cin >> num_vec[n_idx]; // dfs 수행 dfs(num_vec, group, n); int answer = 0; for (int n_idx = 1; n_idx <= n; n_idx++) if (group[n_idx] < 0 ) answer++; cout << answer << "\n"; } return 0; } | cs |