백준 1613번 : 역사 (C언어)

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

1613번: 역사

Code:

#include <stdio.h>
#define INF 987654321
 
int main()
{
    int n, k;
    int arr[401][401] = { 0, };
    int start, end;
    scanf("%d %d", &n, &k);
    while (k--)
    {
        scanf("%d %d", &start, &end);
        arr[start][end] = -1;
        arr[end][start] = 1;
    }
    for (int a = 1; a <= n; a++)
    {
        for (int b = 1; b <= n; b++)
        {
            for (int c = 1; c <= n; c++)
            {
                if (b != c)
                {
                    if (arr[b][a] == -1 && arr[a][c] == -1)
                    {
                        arr[b][c] = -1;
                        arr[c][b] = 1;
                    }
                    if (arr[b][a] == 1 && arr[a][c] == 1)
                    {
                        arr[b][c] = 1;
                        arr[c][b] = -1;
                    }
                }
            }
        }
    }
    int s=0;
    scanf("%d", &s);
    while (s--)
    {
        scanf("%d %d", &start, &end);
        printf("%d\n", arr[start][end]);
    }
    return 0;
}

문제풀이 :

플로이드 워셜 알고리즘을 이용하였다. 첫 2배열에 입력시 앞이 빠르면 -1 뒤가 빠르면 1로 값을 넣어주고

3중 for문 안에서 노드의 연결을 파악하여 값을 채워주었다.

https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 나무위키

알고리즘 참고 바랍니다.