[백준] 1613번 C/C++ 풀이 _ 역사

[백준] 1613번 C/C++ 풀이 _ 역사
카테고리 Algorithm
제목 [백준] 1613번 C/C++ 풀이 _ 역사
작성시간 2018-11-16 00:29:36 +0900
조회수 262

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

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB4549138496530.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

출처

























풀이

이 문제는 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 + 10);
    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







▼discuss 댓글▼



▼facebook 댓글▼