[C] 11403: 경로 찾기

문제는 정점 (i,j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 확인하는 프로그램을 짜야한다.

 

 여기서 알아야할 알고리즘은 Floyd's Algorthim으로 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 사용이 가능한 알고리즘이다. 2차원 배열에 저장을 하며 노드의 개수가 N개라고 할 때 N번만큼의 단계를 반복하여 리스트를 갱신하기 때문에 DP라고 볼 수도 있다.

 이 알고리즘의 점화식은 Dab=min(Dab,Dak+Dkb)이지만 이 문제를 풀 때는 최단 경로가 아닌 경로가 있는지 확인만 하면 되기 때문에 코드가 조금 다를 수 있다. 그리고 이 점화식의 시간복잡도는 O(n^3)이다.

 

#include <stdio.h>
#include <string.h>

int graph[101][101];

int main(void)
  {
    int n;
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
      {
        for(int i=1;i<=n;i++)
          {
            scanf("%d",&graph[j][i]);
          }
      }

    for(int i=1;i<=n;i++) //찍고 가야할 노드
      {
          for(int j=1;j<=n;j++) //출발 노드
            {
              for(int k=1;k<=n;k++) //도착 노드
                {
                  if(j==i|| k==i) //i번째 노드를 찍고 가게 만들어야함, 
                    continue;
                  if(graph[j][i]==1 && graph[i][k]==1) //찍고 갈 수 있으면 1!!
                  {
                    graph[j][k]=1;
                  }
                }
            }
      }

    for(int j=1;j<=n;j++)
      {
        for(int i=1;i<=n;i++)
          {
            printf("%d ",graph[j][i]);
          }
        printf("\n");
      }

    
  }