1613번 역사

처음에 단순히 BFS 문제인줄 알았다.

그러나, 제출을 해보니 시간 초과가 떴다.

BFS를 2번 실행해서 그런 것 같다.

결국 플로이드 와샬 알고리즘 풀어야 한다.

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

<시간 초과 코드 : 틀림>

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<vector<int> > v;
 
vector<int> result;
 
int n = 0, k = 0, s = 0;
 
bool BFS(int s, int e)
{
    queue<int> q;
 
    bool visit[401] = { false, };
 
    q.push(s);
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (here == e) return true;
 
            if (visit[here]) continue;
 
            visit[here] = true;
 
            for (int next : v[here])
            {
                if (!visit[next]) q.push(next);
            }
        }
    }
 
    return false;
}
 
int main(void)
{
    int sv = 0, ev = 0;
 
    scanf("%d %d", &n, &k);
 
    v.resize(n + 1);
 
    while (k--)
    {
        scanf("%d %d", &sv, &ev);
 
        v[sv].push_back(ev);
    }
 
    scanf("%d", &s);
 
    while (s--)
    {
        scanf("%d %d", &sv, &ev);
 
        bool go = BFS(sv, ev);
 
        if (go) result.push_back(-1);
        else
        {
            go = BFS(ev, sv);
 
            if (go) result.push_back(1);
            else result.push_back(0);
        }
    }
 
    for (int i : result)
    {
        printf("%d\n", i);
    }
 
    return 0;
}

<플로이드 와샬 알고리즘 코드 : 정답>

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
 
using namespace std;
 
int incident[401][401] = { 0, };
 
int n = 0, k = 0, s = 0;
 
vector<int> ans;
 
void FloydWarshall()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == j || j == k || k == i) continue;
 
                if (incident[i][j] == 0) // 0인 경우만 따지면 된다. 나머지는 이미 사건이 발생한 후임.
                {
                    if (incident[i][k] == -1 && incident[k][j] == -1)
                    {
                        // i가 k보다 먼저 일어나고, k가 j보다 먼저 일어났으면
 
                        // i가 j보다 먼저 일어났다.
                        incident[i][j] = -1;
                    }
                    else if (incident[i][k] == 1 && incident[k][j] == 1)
                    {
                        // k가 i보다 먼저 일어나고, j가 k보다 먼저 일어났으면
 
                        // j가 i보다 먼저 일어났다.
                        incident[i][j] = 1;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
    int sv = 0, ev = 0;
 
    memset(incident, false, sizeof(incident));
 
    scanf("%d %d", &n, &k);
 
    while (k--)
    {
        scanf("%d %d", &sv, &ev);
 
        incident[sv][ev] = -1; // sv가 ev보다 먼저 일어남.
        incident[ev][sv] = 1; // ev가 sv보다 먼저 일어남.
    }
 
    FloydWarshall();
 
    scanf("%d", &s);
 
    while (s--)
    {
        scanf("%d %d", &sv, &ev);
 
        ans.push_back(incident[sv][ev]);
    }
 
    for (int i : ans)
    {
        printf("%d\n", i);
    }
 
    return 0;
}