[11403번] 경로 찾기 (플로이드 워셜 알고리즘)

문제 출처 :

https://www.acmicpc.net/problem/11403

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘

플로이드 워셜 개념 :: http://www.crocus.co.kr/536

플로이드 워셜 소스 코드 :: http://www.crocus.co.kr/537

이 문제는 플로이드 워셜 알고리즘을 이용하면 충분히 풀린다.

N의 최대가 100이기에 100 * 100 * 100 = 100만이기에 시간제한에도 문제없고,

i->j로 갈수있는지 확인하기 위해 플로이드 워셜 알고리즘으로 최단 거리가 생성되는지만 확인하면된다.

0을 넣는다는 의미는 무한대를 의미하고, 그 외에는 최단 거리가 나타나게 되지만, 결과를 출력할 때는

최단 거리를 출력하는 것이 아닌, 최단 거리가 존재한다면 1, 없다면(무한대라면) 0을 출력하면 되는 문제이다. 

소스 코드 : 

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 97 98

#include<stdio.h> #include <limits.h>   // 정점의 수를 지정한다. int V;   // INF를 무한대라고 지정하고, INT_MAX를 이용한다. #define INF 10000       // 플로이드 워셜의 결과를 출력하는 함수 void printSolution(int dist[][101]) {     for (int i = 0; i < V; i++)     {         for (int j = 0; j < V; j++)         {             if (dist[i][j] == INF)                 printf("0 ");             else                 printf("1 ");         }         printf("\n");     } }     // 모든 경로에 대한 최단 거리를 찾아주는 플로이드 워셜 함수 void floydWarshall(int graph[][101]) {     /*     dist[][] 배열에 최단 거리에 대한 정보들이 모두 들어가게 된다.     */     int i, j, k;       int dist[101][101];       /*     dist[][] 배열에 초기값은 그래프에서 주어진 값들이다.     (즉, 아직 최단 거리를 구하기 전에는 기존의 거리를 최단 거리라 생각한다.)     */     for (i = 0; i < V; i++)         for (j = 0; j < V; j++)             dist[i][j] = graph[i][j];           /*     플로이드 워셜 알고리즘의 핵심     */     // 한 점을 경유하여     for (k = 0; k < V; k++)     {         // x에서         for (i = 0; i < V; i++)         {             // y로 갈때             for (j = 0; 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 val;       scanf("%d", &V);       // 그래프 정보 입력     for (int i = 0; i < V; i++)         for (int j = 0; j < V; j++)         {             scanf("%d", &val);             val == 0 ? graph[i][j] = INF : graph[i][j] = val;         }         // 플로이드 워셜 알고리즘으로 진입     floydWarshall(graph);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus