[C언어] 백준 11403 : 경로 찾기

백준 11403 : 경로 찾기

 

문제 링크

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

 

문제 내용

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

 

 

Idea

플로이드 알고리즘은 정점 간의 최단 경로(가중치)를 구하는 알고리즘이지만 이런 경로의 유무를 따지는 문제에도 적용하면 금세 풀 수 있다.

 

플로이드 알고리즘에 대해 간단히 설명하자면, 다이나믹 프로그래밍과 비슷하다. 우선 이 알고리즘의 포인트는 간선이 존재하지 않는 부분은 매우 큰 값을 주어야 한다는 점이다. (최소 가중치를 구하기 때문이다)

 

정점 u에서 v로 가는 최단거리를 구하고자 한다. 이때, 어떠한 정점 k가 있다면 아래와 같은 경우가 생긴다

1. 정점 k를 거쳐서 간다.
2. 정점 k를 거치지 않는다.

따라서, dist[u][v]가 정점 u에서 v로 가는 최단 거리라고 한다면 다음과 같은 식을 만들 수 있다.

• dist[u][v] = MIN(dist[u][v], dist[u][k] + dist[k][v])

※ 만약 최종 결과 값이 매우 큰 값(초기 설정값)이라면 정점 u에서 v로 가는 경로가 없음을 뜻한다.

 

 

Code

#include <stdio.h>
#define INF 987654321
#define MIN(a,b) a<b?a:b
int arr[100][100];
 
int main() {
    int N;
    scanf("%d", &N);
 
    //인접행렬 입력받기
    //간선이 없다면 가장 큰 수를 삽입
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 0) arr[i][j] = INF;
        }
    }
 
    //플로이드 알고리즘
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = MIN(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
 
    //결과 출력
    //결과가 가장 큰 수라면 경로가 없다는 뜻이므로 0
    //그 외에는 1
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == INF) printf("0 ");
            else printf("1 ");
        }
        printf("\n");
    }
 
 
    return 0;
}