2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
처음에 이 그림을 보았을 때 위상정렬을 쓰는건가 하고 생각했었지만 순서 중 하나를 출력하는 것이 아닌 자신의 정확한 순서를 알고있는 학생의 수를 출력하는 문제였습니다.
저는 두 가지 방법으로 해결하였습니다.
먼저 dfs 방법입니다.
저는 2개의 벡터를 사용하였습니다. (자신보다 키가 큰 학생을 저장하는 벡터(f), 작은 학생을 저장하는 벡터(s))
한 학생을 시작으로 두번의 dfs를 수행합니다.
i번 학생보다 키가 큰 학생들을 dfs로 순회하고, 작은 학생들도 똑같이 dfs로 순회합니다.
순회하면서 next의 갯수만큼 cnt를 1씩 늘려줍니다.
두 번의 dfs가 끝나고 cnt가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.
그 다음은 플로이드 방법입니다.
d[i][j] : i번 학생의 키 < j번 학생의 키 인 경우
플로이드로 자신보다 키가 큰 학생들을 모두 구합니다.
그 다음 i번 학생과 j번 학생의 관계를 확인합니다.
d[i][j] (i번이 j번보다 작은 경우) || d[j][i] (i번이 j번보다 큰 경우)
위의 조건을 만족한 횟수가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.
아무래도 플로이드가 N^3이라 dfs에 비해 속도가 느린 편입니다.
[dfs]
|
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
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<int> f[501], s[501];
bool visit[501];
int N, M, cnt;
void dfs(vector<int> t[], int v) {
visit[v] = true;
for (int i = 0; i < t[v].size(); i++) {
int next = t[v][i];
if (visit[next]) continue;
cnt++;
dfs(t, next);
}
}
void func() {
int ans = 0;
for (int i = 1; i <= N; i++) {
memset(visit, false, sizeof(visit));
dfs(f, i);
memset(visit, false, sizeof(visit));
dfs(s, i);
if (cnt == N - 1) ans++;
cnt = 0;
}
cout << ans << '\n';
}
void input() {
int u, v;
cin >> N >> M;
while (M--) {
cin >> u >> v;
f[u].push_back(v);
s[v].push_back(u);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[플로이드]
|
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
|
#include <iostream>
#define INF 1000000000
using namespace std;
bool d[501][501];
int N, M, ans;
void solve() {
for (int i = 1; i <= N; i++) {
int cnt = 0;
for (int j = 1; j <= N; j++) {
if (d[i][j] || d[j][i]) cnt++;
}
if (cnt == N - 1) ans++;
}
cout << ans << '\n';
}
void func() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (d[i][k] && d[k][j]) {
d[i][j] = true;
}
}
}
}
}
void input() {
int u, v;
cin >> N >> M;
while (M--) {
cin >> u >> v;
d[u][v] = true;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
solve();
return 0;
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 19236 청소년 상어 (0) | 2021.04.22 |
|---|---|
| boj 2239 스도쿠 (0) | 2021.04.16 |
| boj 14889 스타트와 링크 (0) | 2021.03.17 |
| boj 2023 신기한 소수 (0) | 2021.03.16 |
| boj 14500 테트로미노 (0) | 2021.03.15 |