반응형
문제 출처 :
https://www.acmicpc.net/problem/2606
알고리즘 분석 :
문제 해결에 필요한 사항
1. 플로이드 워셜 알고리즘
플로이드 워셜 개념 :: http://www.crocus.co.kr/536
플로이드 워셜 소스 코드 :: http://www.crocus.co.kr/537
플로이드 워셜 알고리즘은 x->y의 최단 거리를 찾아주는것이다.
이것을 자세히 생각해보면 결국 이 말은 x->y를 연결할 수 있는지 묻는 문제이고,
연결이 된다면 최단 거리가 찾아진다는 의미를 이용하여 이 문제를 푼다.
소스 코드 :
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<stdio.h> #include <limits.h> // 정점의 수를 지정한다. int V; // INF를 무한대라고 지정하고, INT_MAX를 이용한다. #define INF 10000 int cnt; // 플로이드 워셜의 결과를 출력하는 함수 void printSolution(int dist[][101]) { for (int j = 2; j <= V; j++) dist[1][j] == INF ? 0 : cnt++; printf("%d", cnt); } // 모든 경로에 대한 최단 거리를 찾아주는 플로이드 워셜 함수 void floydWarshall(int graph[][101]) { /* dist[][] 배열에 최단 거리에 대한 정보들이 모두 들어가게 된다. */ int i, j, k; int dist[101][101]; /* dist[][] 배열에 초기값은 그래프에서 주어진 값들이다. (즉, 아직 최단 거리를 구하기 전에는 기존의 거리를 최단 거리라 생각한다.) */ for (i = 1; i <= V; i++) for (j = 1; j <= V; j++) dist[i][j] = graph[i][j]; /* 플로이드 워셜 알고리즘의 핵심 */ // 한 점을 경유하여 for (k = 1; k <= V; k++) { // x에서 for (i = 1; i <= V; i++) { // y로 갈때 for (j = 1; j <= V; j++) { // 최단거리면 업데이트 해준다. // 이 문제에서는 최단거리라기 보다는 이어져있다고 생각한다. if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } // 모든 최단거리가 구해지고 난 뒤, 출력을 해준다. printSolution(dist); } int main() { int graph[101][101]; int from, to, n; scanf("%d", &V); scanf("%d", &n); for (int i = 1; i <= V; i++) for (int j = 1; j <= V; j++) i == j ? graph[i][j] = 0 : graph[i][j] = INF; for (int i = 0; i < n; i++) { scanf("%d %d", &from, &to); graph[from][to] = 1; graph[to][from] = 1; } // 플로이드 워셜 알고리즘으로 진입 floydWarshall(graph); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[13701번] 중복 제거 (0) | 2016.11.22 |
---|---|
[1753번] 최단 경로 (0) | 2016.11.21 |
[11657번] 타임머신 (벨만 포드 알고리즘) (0) | 2016.11.18 |
[11403번] 경로 찾기 (플로이드 워셜 알고리즘) (0) | 2016.11.18 |
[2003번] 수들의 합 2 (2) | 2016.11.18 |