백준 1613 : 역사

문제 설명

---

사건의 개수와 사건 간의 전후 관계가 주어진다. 이때 주어진 전후 관계를 바탕으로 다른 사건들 간의 전후 관계를 유추할 수 있는지 확인해야한다. 예측할 수 있는지 여부를 확인해 각각의 쿼리에 대해 답한다.

---

 

 이 문제는 플로이드-워셜 알고리즘을 사용하는것이 편하다.(처음에 BFS로 풀어보려다 실패해 슬펐다)모든 사건 쌍에 대해 전후 관계를 효율적으로 계산할 수 있기 때문이다.

그래프를 주어진 정방향으로 하나, 역방향으로 하나 총 2개를 만들어 이를 통해 사건의 전후관계를 파악할 수 있다.

각각 주어진 쿼리에 대해 시작점과 끝점이

정방향 그래프에서 이어져 있다면 "-1"

역방향 그래프에서 이어져있다면 "1"

둘다 이어져있지 않다면 "0"

을 출력한다.

---

소스 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n, k;
int ch1[410][410], ch2[410][410];

int main()
{
    int i, j, m;
    scanf("%d %d", &n, &k);
    for(i=0;i<k;i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ch1[x][y] = 1;
        ch2[y][x] = 1;
    }
    for(m=1;m<=n;m++) {
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                if(ch1[i][j] == 1) continue;
                if(ch1[i][m] == 1 && ch1[m][j] == 1) {
                    ch1[i][j] = 1;
                }
            }
        }
    }
    for(m=1;m<=n;m++) {
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                if(ch2[i][j] == 1) continue;
                if(ch2[i][m] == 1 && ch2[m][j] == 1) {
                    ch2[i][j] = 1;
                }
            }
        }
    }
    int Q;
    scanf("%d", &Q);
    while(Q--) {
        int x, y;
        scanf("%d %d", &x, &y);
        if(ch1[x][y] == 1) printf("-1\n");
        else if(ch2[x][y] == 1) printf("1\n");
        else printf("0\n");
    }
    return 0;
}