문제

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

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

입력

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

출력

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

접근 과정

처음에는 링크드 리스트의 형태로 순서를 정렬해야하나 싶었으나 주어지는 입력을 그래프 형태로 정리해 너비 우선 탐색(BFS)를 수행하면 사건간의 전후관계를 파악할 수 있을 것 같았다.
BFS를 사용해 제출하였으나 시간초과. 중복되는 탐색이 많아 DP를 적용해볼까 하는 생각도 들었지만 정점 수가 최대 400개 밖에 되지 않아 문제가 될 것 같진 않았다.
생각해보니 문제에서 실행 중 입출력이 잦았다. C++ iostream의 cin과 cout을 사용한 입출력이 C의 표준 입출력에 비해 속도가 느리다는 점이 떠올랐고 iostream의 함수들을 sdtio.h 함수로 교체한 결과 무리 없이 통과할 수 있었다.
이번에도 더 빠른 실행 속도의 풀이들이 보여서 검색을 통해 다른 사람들의 풀이를 살펴보았는데 모두 플로이드 와샬 알고리즘을 적용하여 문제를 풀고 있었다. 본인은 플로이드 와샬을 별로 사용해본적이 없어서 적용할 생각을 못했는데 공부했던 알고리즘들의 사용처와 장단점을 다시 복습해볼 필요가 있을 것 같다.

소스 코드

#include <cstring>
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;

int checkOrder(int n, vector<int>* graph, int prev, int next) {
    static bool bVisited[501];
    queue<int> vertices;

    memset(bVisited + 1, 0, n);

    vertices.push(prev);
    bVisited[prev] = true;
    while (!vertices.empty()) {
        int& vertex = vertices.front();

        for (unsigned int i = 0; i < graph[vertex].size(); ++i) {
            int& v = graph[vertex][i];
            if (v == next) {
                return -1;
            }

            if (!bVisited[v]) {
                vertices.push(v);
                bVisited[v] = true;
            }
        }
        vertices.pop();
    }

    vertices.push(next);
    bVisited[next] = true;
    while (!vertices.empty()) {
        int& vertex = vertices.front();

        for (unsigned int i = 0; i < graph[vertex].size(); ++i) {
            int& v = graph[vertex][i];
            if (v == prev) {
                return 1;
            }

            if (!bVisited[v]) {
                vertices.push(v);
                bVisited[v] = true;
            }
        }
        vertices.pop();
    }

    return 0;
}

int main() {
    int n, k, s;
    int prev, next;
    vector<int> graph[501];

    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; ++i) {
        scanf("%d %d", &prev, &next);
        graph[prev].push_back(next);
    }

    scanf("%d", &s);
    for (int i = 0; i < s; ++i) {
        scanf("%d %d", &prev, &next);
        printf("%d\n", checkOrder(n, graph, prev, next));
    }

    return 0;
}