역사
https://www.acmicpc.net/problem/1613
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 13395 | 4248 | 3117 | 34.196% |
문제
역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다.
즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.
세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까?
이를 해결하는 프로그램을 작성해 보도록 하자.
입력
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다.
다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.
이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다.
물론 사건의 전후 관계가 모순인 경우는 없다.
다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다.
다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다.
사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
s줄에 걸쳐 물음에 답한다.
각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1,
뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.
예제 입력 1
5 5 1 2 1 3 2 3 3 4 2 4 3 1 5 2 4 3 1
예제 출력 1
0 -1 1
출처
알고리즘 분류
접근 방법
통과된 코드
#include <iostream> #include <vector> #include <list> using namespace std; int n, k, f, b, s; constexpr int MAX = 401; vector<pair<int, int>> graph[MAX]; list<pair<int, int>> myList; int disArr[MAX][MAX]; int main() { ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화 // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다. cin.tie(NULL); cout.tie(NULL); cin >> n >> k; // 사건의 전후 관계 입력 for (int i = 0; i < k; i++) { cin >> f >> b; graph[f].push_back(make_pair(b, -1)); graph[b].push_back(make_pair(f, 1)); // 역방향 가능 } // 질문을 입력 받는다. cin >> s; pair<int, int> tempP; while (s--) { // 문제를 입력받는다. cin >> tempP.first >> tempP.second; myList.push_back(tempP); } for (int i = 1; i <= n; i++) { for (int j = 0; j < graph[i].size(); j++) { int v = graph[i][j].first; int weight = graph[i][j].second; disArr[i][v] = weight; } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) disArr[i][j] = 0; else if (disArr[i][k] == 1 && disArr[k][j] == 1) disArr[i][j] = 1; else if (disArr[i][k] == -1 && disArr[k][j] == -1) disArr[i][j] = -1; } } } for (auto it = myList.begin(); it != myList.end(); it++) { cout << disArr[it->first][it->second] << "\n"; } return 0; }