[2606번] 바이러스 (플로이드 워셜 알고리즘)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

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

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

플로이드 워셜 알고리즘은 x->y의 최단 거리를 찾아주는것이다.

이것을 자세히 생각해보면 결국 이 말은 x->y를 연결할 수 있는지 묻는 문제이고, 

연결이 된다면 최단 거리가 찾아진다는 의미를 이용하여 이 문제를 푼다.

소스 코드 : 

#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 >>