# 2458. 키 순서 [링크](https://www.acmicpc.net/problem/2458) | 난이도 | 정답률(\_%) | | :----: | :---------: | | Gold IV | 51 | ## 설계 ### 플로이드-워셜 알고리즘 플로이드 워셜 알고리즘은 모든 정점 쌍에 대한 최단거리를 구하는 알고리즘이다. 플로이드 워셜 알고리즘을 수행하면, 모든 정점에 대한 연결 여부와 거리를 판단할 수 있다. 따라서 플로이드 워셜 알고리즘을 통해 모든 정점상의 거리를 구한다. ### 단방향 그래프 키 순서에 대한 그래프이므로 그래프는 단방향 그래프이다. 거리를 구한 그래프에서, [i][j]의 거리와 [j][i]거리 모두 무한인 경우가 (정점 i와 j는 절대 연결되지않으) 존재하면 이는 답이 될 수 없다. 1부터 N까지 n을 순회하고, j또한 한번 더 순회하며 [n][j]와 [j][n]이 모두 무한인지 비교하고, 모두 무한인 경우가 없는 경우 정답을 증가시킨다 ## 정리 | 내 코드 | 빠른 코드 | | :-----: | :-------: | | 104 ms | | ## 고생한 점 ## 코드 ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> #define INF 1e9 using namespace std; int graph[501][501]; void solution() { int N, M; int answer = 0; cin >> N >> M; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { graph[i][j] = i == j ? 0 : INF; } } for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; graph[a][b] = 1; } for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (graph[i][j] > graph[i][k] + graph[k][j]) { graph[i][j] = graph[i][k] + graph[k][j]; } } } } for (int i = 1; i <= N; i++) { bool canJudge = 1; for (int j = 1; j <= N; j++) { if (graph[i][j] == INF && graph[j][i] == INF) { canJudge = 0; break; } } if (canJudge) answer++; } cout << answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity