반응형
https://www.acmicpc.net/problem/2458
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr [ 501 ][ 501 ] 배열을 만들고 값을 987654321로 초기화합니다.
2. 키 순서를 입력 받고, arr [ a ][ b ] = 1로 초기화합니다.
3. 플로이드 와샬 알고리즘을 통해 각 노드 간의 거리를 저장합니다.
4. 2중 for문을 통해 arr[arr [ i ][ j ] == 987654321 && arr [ j ][ i ] == 987654321인 경우 키를 비교할 수 없으므로 제외하고, 모든 노드에 관하여 아닐 경우 ans++를 해줍니다.
5. ans를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int N, M; int arr[501][501]; int main() { scanf("%d %d", &N, &M); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { arr[i][j] = 987654321; } } for (int i = 0; i < M; i++) { int a, b; scanf("%d %d", &a, &b); arr[a][b] = 1; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { if (arr[j][k] > arr[j][i] + arr[i][k]) { arr[j][k] = arr[j][i] + arr[i][k]; } } } } int ans = 0; for (int i = 1; i <= N; i++) { int flag = 0; for (int j = 1; j <= N; j++) { if (i != j) { if (arr[i][j] == 987654321 && arr[j][i] == 987654321) { flag = 1; break; } } } if (flag == 0) ans++; } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2637번 - 장난감 조립 (C++) (0) | 2023.02.09 |
|---|---|
| [ 백준 ] 11658번 - 구간 합 구하기 3 (C++) (0) | 2023.02.08 |
| [ 백준 ] 2211번 - 네트워크 복구 (C++) (0) | 2023.02.06 |
| [ 백준 ] 17835번 - 면접보는 승범이네 (C++) (0) | 2023.02.05 |
| [ 백준 ] 1368번 - 물대기 (C++) (0) | 2023.02.04 |