11403 경로 찾기

11403 경로 찾기 (c++)

문제

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

접근 방식

플로이드 워셜 알고리즘 i 에서 k 를 거쳐 j 로 갈 수 있는지 O(n^3)

문제 풀이

#include <stdio.h>

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

다시 생각해볼 점

1. 처음에 플로이드-워셜 알고리즘에 이상한 조건식 붙여서 실패했었다. (그냥 k,i,j순으로 반복해서 단순하게 끝내자)