출처 : https://www.acmicpc.net/problem/1613
역사 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 4549 | 1384 | 965 | 30.890% |
문제
역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.
세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.
입력
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다.
출력
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
출처
- 문제를 만든 사람: author5
풀이
이 문제는 BFS or 플로이드 와샬을 통하여 문제를 해결할 수 있습니다.
BFS를 이용하여 부모 자식간의 노드 관계를 기록해주면서 bfs를 돌면 시간내에 통과할 수 있습니다.(힘겹게)
is_first_idx_parent[idx_1][idx_2] 에서 idx_1 이 idx_2 의 부모이면 1로 기록해주었습니다.
플로이드 와샬은 상대적으로 빠른 시간 내에 문제를 해결할 수 있습니다.
자세한 내용은 소스코드를 참고해주세요!!
BFS 소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> #include <vector> #include <queue> using namespace std; // global vector<vector<int>> node_edge; vector<vector<int>> is_first_idx_parent; int is_have_node(int _n, int _node_1, int _node_2) { vector<int> is_visited(_n + 1, 0); queue<int> bfs_queue; bfs_queue.push(_node_1); // 이미 노드가 자식 노드인 것을 파악했다면 if(is_first_idx_parent[_node_1][_node_2]) return 1; int bfs_size = bfs_queue.size(); while (bfs_size--) { int now_node = bfs_queue.front(); bfs_queue.pop(); // 찾는 노드면 if (now_node == _node_2) return 1; // 방문한 노드면 if (is_visited[now_node]){ // 라운드 갱신 if (bfs_size == 0) bfs_size = bfs_queue.size(); continue; } is_visited[now_node] = 1; // 연결된 노드 모두 넣기 for (auto next_node : node_edge[now_node]){ is_first_idx_parent[_node_1][next_node] = 1; is_first_idx_parent[now_node][next_node] = 1; bfs_queue.push(next_node); } // 라운드 갱신 if (bfs_size == 0) bfs_size = bfs_queue.size(); } return 0; } int main() { int n, k; scanf("%d %d", &n, &k); node_edge.resize(n + 1); is_first_idx_parent.resize(n+1); for (int idx = 0; idx < n + 1; idx++) is_first_idx_parent[idx] = vector<int>(n+1); for (int k_idx = 0; k_idx < k; k_idx++) { int before, after; scanf("%d %d", &before, &after); node_edge[before].push_back(after); } int s; scanf("%d", &s); for (int s_idx = 0; s_idx < s; s_idx++) { int node_1, node_2; scanf("%d %d", &node_1, &node_2); // 한 쪽에서 다른 한 쪽을 찾을 때 까지 자식을 계속 찾는다. if (is_have_node(n, node_1, node_2)) printf("-1\n"); else if (is_have_node(n, node_2, node_1)) printf("1\n"); else printf("0\n"); } return 0; } | cs |
플로이드 와샬 소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <stdio.h> int n, history[401][401]; void solve(){ int i, j, k; for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (history[i][k] == 1 && history[k][j] == 1) history[i][j] = 1, history[j][i] = -1; } int main() { int m, i, before, after; scanf("%d %d", &n, &m); for (i = 0; i < m; i++) { scanf("%d %d", &before, &after); history[before][after] = -1; history[after][before] = 1; } solve(); scanf("%d", &m); for (i = 0; i < m; i++) { scanf("%d %d", &before, &after); printf("%d\n", history[before][after]); } return 0; } | cs |