[BOJ-1613]역사

[출처]

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

[문제요약]

두 사건의 전 후 관계를 알려준다. 

주어진 사건들의 전 후 관계로 질문으로 주어지는 두 사건의 전 후 관계를 알아내야 한다.

[입력]

N K - N~[1,400] : 사건의 개수 , K~[1,50000] : 사건의 전후 관계의 개수

A1 B1 : Ai 사건은 Bi 사건보다 먼저 일어났음을 의미한다.

..

AK BK : 사건의 전후 관계 개수 K개가 입력된다.

S~[1, 50000]  : 질문의 개수가 주어진다.

X1 Y1 : 질문이 주어지며, 서로 다른 두 사건이 번호가 주어진다. 

..

XS YS 

[출력]

질문으로 주어지는 X Y 사건 간의 관계를 질문번호에 맞춰 출력한다. 

X Y 순으로 사건이 일어났다면 -1

Y X 순으로 사건이 일어났다면 1

두 사건간의 관계를 유추할 수 없다면 0 을

출력한다. 

[접근방법]

입력으로 주어지는 사건관계를 행렬로 만든다. [before][after] 관계라면 -1 을 저장하고, [after][before] 관계라면 1을 저장한다.

이제 이 정보를 이용하여 모든 경우를 알기위해 플로이드-와샬 알고리즘을 이용한다. 

이때 경우는 아래와 같다.

사건1 중간사건 사건2 순으로 있다고 하고, 중간사건은 경유지와 같다고 하자.

1) 관계 [1, 중간] 사건1 > 중간사건

2) 관계 [중간, 2] 중간사건 > 사건2

3) 관계 [1   ,   2]사건1 > 사건2 

[조건]

관계 [1, 중간] 와 [중간, 2] 이 1 이면, [1,2] 사건은 1로 관계를 맺을 수 있다.

또한, 

관계 [1, 중간] 와 [중간, 2] 이 -1 이면, [1,2] 사건은 -1로 관계를 맺을 수 있다.

하지만 모든 중간사건을 먼저 다 탐색해서 플로이드-워셜을 작성해야하므로, 한 중간지점을 정했을 때, 사건1 과 사건2을 모두 완전탐색해야한다.

그렇기에 

for(중간지점)

     for(사건1)

          for(사건2) 

순서로 플로이드 워셜 알고리즘을 진행해야 한다.

그리고 [조건]을 넣어주면 이미 구해진 행렬에서 질문에 맞게 답을 꺼내어 출력해주면 된다.

처음 접근 시 BFS 로 풀이해보려 했다. before, after 순서로 구성된 두 인접리스트를 만들고 탐색을 하였다.

  하지만 질문이 주어질 때마다 탐색을 진행해야 함으로 '시간초과(TLE)'를 받을 것으로 생각했지만, 잘못 작성한 부분이 있는지 WA를 받아 바로 플로이드-와샬 알고리즘으로 풀이하였다. 

[C++11 source Code Floyd-Warshall]

#include<cstdio>
#define din1(a) scanf("%d", &a)
#define din2(a,b) scanf("%d%d", &a, &b)
using namespace std;
 
const int M = 444;
 
int imap[M][M];
 
void print_map(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%3d", imap[i][j]);
        }
        puts("");
    }
}
 
int main() {
    int n, k, q, a, b;
    din2(n, k);
    for (int i = 0; i < k; i++) {
        din2(a, b);
        imap[a][b] = -1;
        imap[b][a] = 1;
    }
 
    //print_map(n);
    //puts("after");
    // fw
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (imap[i][k] == 1 && imap[k][j] == 1) {
                    imap[i][j] = 1;
                    imap[j][i] = -1;
                }
                else if (imap[i][k] == -1 && imap[k][j] == -1) {
                    imap[i][j] = -1;
                    imap[j][i] = 1;
                }
            }
        }
    }
 
    //print_map(n);
 
    din1(q);
    for (int query = 0; query < q; query++) {
        din2(a, b);
        printf("%d\n", imap[a][b]);
    }
 
    return 0;
}