11403번: 경로 찾기

11403번: 경로 찾기

사용 언어: C

문제 요약

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해 i -> j 로 가는 양수의 경로가 있는지 구하는 프로그램을 작성하시오.

풀이

일단 문제에서 모든 정점에 대해 어떠한(모든) 길로 가는지 알아내라는 문제. 일단 그래프 문제인건 확실하고, 그 중에서 BFS, DFS, Dijkstra, 플로이드 워셜 등을 생각해볼 수 있는데 이런 경우 (모든 -> 모든)을 검사하는 문제는 플로이드 워셜이 적합하다.

플로이드 워셜은 모든 정점 쌍에 대한 최단 경로를 구하는게 원래 목적인데, 해당 문제에서는 단순히 경로가 존재하는지로만 쓸 것이다.

원리:

1. i -> j 로 가는 기존 경로 거리 arr[i][j]

2. 중간 노드 k를 거쳐 i -> k -> j 경로를 고려

3. arr[i][j] = min( arr[i][j], arr[i][k] + arr[k][j] )

 

원래라면 위 3단계를 따라가지만 해당 문제는 경로만 파악하므로 경로 존재여부를 1,0으로 갱신하는 방식으로만 변형할 것이다.

그래서 3번 -> if(arr[i][k] && arr[k][j]) arr[i][j] = 1;

답

#include <stdio.h>

int main()
{
    int N;
    scanf("%d",&N);
    
    int arr[N][N];
    
    for (int i = 0; i < N; i++) 
    {
        for (int j = 0; j < N; j++) 
        {
            scanf("%d", &arr[i][j]);
        }
    }
    
    for(int m=0; m<N; m++)
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(arr[i][m] && arr[m][j])
                {
                    arr[i][j] = 1;
                }
            }
        }
    }
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }

    return 0;
}