백준) 1613 : 역사

문제 링크: https://www.acmicpc.net/problem/1613

1613번: 역사

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k 줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s 줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이>>

키 순서와 똑같은 문제이다. 다른 점은 앞에 일어난 사건이 먼저냐 뒤에 사건이 먼저냐에 따라 조건문을 추가해주어야 한다.

#include<iostream>
#include<cstdio>
using namespace std;
int map[401][401];
 
int main()
{
    int i,j,k;
 
    int N , K;
 
    scanf("%d%d" , &N ,&K);
 
    int x, y;
 
    for( i = 1; i<= K ; i++)
    {
        scanf("%d%d" ,&x ,&y);
        map[x][y] = 1;
    }
 
        for( k = 1; k<=N ; k++)
        for( i = 1; i<=N ; i++)
        for( j = 1; j<=N ; j++)
        {
            if( i == j || i == k || j == k ) continue;
 
            if(map[i][k] && map[k][j]) map[i][j] = 1;
        }
 
    int so ;
    scanf("%d",&so);
 
    for( i =1 ; i<= so ;i++)
    {
        scanf("%d%d" , &x,&y);
 
        if(map[x][y] == 1 && map[y][x] == 0  )
            printf("-1\n");
 
            else if(map[x][y] == 0 && map[y][x] == 1)
            printf("1\n");
            else if(map[x][y] == 0 && map[y][x] == 0)
            printf("0\n");
    }
 
 
 
 
    return 0;
}