문제 링크 :
이 문제 또한 기존의 DFS와 거의 비슷한 방식으로 풀게되는 문제 입니다. 연결 되었는지 확인하는 문제이니까요.
그러나, 기존의 DFS는 이미 방문했던 노드는 더이상 가지 않았었는데,
이 문제의 경우는 기방문한 노드더라도 한번 확인해 주어야 합니다.
그 이유는.. 아무리 기방문한 노드더라도
1. 지목->지목->지목 ... 즉, 돌고돌아서 같은 팀이 되는 경우
2. 그냥 뜬금없이 지목된 경우
이 두가지를 구분 해주어야 합니다.
따라서, trace라는 배열을 따로 선언하여 계속 방문한 노드를 저장해 주며,
방문했던 노드를 또 방문하게 되었다면 1, 2를 구분해 주기 위해..
trace를 순회하며 지금 방문한(기방문 한 바로 지금) 노드 가 발견될 경우 1번.
그 외 2번이므로 함수 종료.
소스코드 :
이 문제 또한 기존의 DFS와 거의 비슷한 방식으로 풀게되는 문제 입니다. 연결 되었는지 확인하는 문제이니까요.
그러나, 기존의 DFS는 이미 방문했던 노드는 더이상 가지 않았었는데,
이 문제의 경우는 기방문한 노드더라도 한번 확인해 주어야 합니다.
그 이유는.. 아무리 기방문한 노드더라도
1. 지목->지목->지목 ... 즉, 돌고돌아서 같은 팀이 되는 경우
2. 그냥 뜬금없이 지목된 경우
이 두가지를 구분 해주어야 합니다.
따라서, trace라는 배열을 따로 선언하여 계속 방문한 노드를 저장해 주며,
방문했던 노드를 또 방문하게 되었다면 1, 2를 구분해 주기 위해..
trace를 순회하며 지금 방문한(기방문 한 바로 지금) 노드 가 발견될 경우 1번.
그 외 2번이므로 함수 종료.
소스코드 :
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
67
68
69
70
71
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
vector<int> trace;
int outsider;
void MakeTeam(int index, vector<int> & v, vector<int> & trace) {
// 아직 방문 안한경우
if (v[index] != 0) {
trace.push_back(index);
int tmp = v[index];
v[index] = 0;
MakeTeam(tmp, v, trace);
}
// 이전에 방문 했던 노드인 경우
else {
int tmp = 0;
// 뜬금없이 너랑 같은팀이 되고 싶어 한 경우와, 돌고돌아 같은팀 된 경우 구분용도의 flag
bool trap = false;
for (int i = 0; i < trace.size(); i++) {
// 돌고돌아 같은팀이되었다.
if (trace[i] == index) {
tmp = i;
trap = true;
break;
}
}
if (trap) {
outsider -= (trace.size() - tmp);
}
else {
return;
}
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
trace.clear();
int n;
cin >> n;
outsider = n;
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 1; i <= n; i++) {
if (v[i] != 0) {
trace.clear();
MakeTeam(i, v, trace);
}
}
cout << outsider << endl;
}
}
| cs |
댓글
댓글 쓰기