쾌락없는 책임 (공부)/알고리즘 문제풀이
백준 1613 역사 - C++
허스크
2021. 5. 28. 19:27
반응형
1613번: 역사
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int n, k, s, from, to;
int pre, aft;
int history[401][401];
vector<pair<int, int>> sol;
void History(){
for(int v = 1; v <= n; v++){
for(int f = 1; f <= n; f++){
for(int t = 1; t <= n; t++){
if(!history[f][t]){
if(history[f][v] == 1 && history[v][t] == 1)
history[f][t] = 1;
else if(history[f][v] == -1 && history[v][t] == -1)
history[f][t] = -1;
}
}
}
}
}
int main(){
scanf("%d %d", &n, &k);
while(k--){
scanf("%d %d", &pre, &aft);
history[pre][aft] = -1;
history[aft][pre] = 1;
}
scanf("%d", &s);
while(s--){
scanf("%d %d", &from, &to);
sol.push_back(make_pair(from, to));
}
History();
for(int i = 0; i < sol.size(); i++)
printf("%d\n", history[sol[i].first][sol[i].second]);
}
전 경로를 구해야 하고 n이 400이니 플로이드-와샬 알고리즘을 이용해서 풀이하게 됩니다. 문제대로 history[i][j]에서 i가 j 보다 먼저 일어난 사건이라고 하면 -1, 나중에 일어난 사건이라고 하면 1이라고 저장하고 문제를 풀이하면 됩니다.
이전 사건과 이후 사건의 앞뒤가 구해진다고 하면 플로이드-와샬처럼 중간 경유지를 넣어서 배열을 업데이트 해주면 됩니다.
반응형