[백준] 1939번 C/C++ 풀이

[백준] 1939번 C/C++ 풀이
카테고리 Algorithm
제목 [백준] 1939번 C/C++ 풀이
작성시간 2018-02-21 00:27:13 +0900
조회수 300

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

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB4891122575624.239%

문제

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 

3

힌트

출처

  • 문제의 오타를 찾은 사람: lg8375
  • 빠진 조건을 찾은 사람: sshstamref

알고리즘 분류


























>> 풀이 방법 

쉬워 보였는데, 상당히 시간이 오래 걸렸다. 
이유를 보니 메모리 초과 때문에 자꾸 에러를 겪었는데, 바보같이 malloc 에서 불필요한 N 을 한 번 더 곱해서
초과가 안될래야 안될 수가 없는 구조였다. 

나는 dfs 를 이용한 풀이를 사용했는데, 해당 풀이는 위의 에러를 제거해보니 시간 초과가 나왔다. 
단순히 dfs를 재귀함수로 구현할 경우에는 경우의 수가 너무 많은 것 같다. 




(1) dfs 를 이용한 시간 초과된 풀이 방법 

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream> 
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef struct EDGE {
    int end_node;
    int weight;
}EDGE;
 
typedef struct NODE {
    int node_num;
    vector<EDGE*>* edge_vec;
}NODE;
 
int N, M;
NODE** node_arr;
int visited[100001];
int answer = 0;
int max_weight = 0;
 
void visited_init() {
    for (int i = 0; i < 100001; i++)
        visited[i] = 0;
}
 
int find_big_weight(int now_edge, int end_edge, int weight) {
    int result = 0
    
    // 끝 노드이면 답에 추가 
    if (now_edge == end_edge) {
        if (answer < weight) answer = weight;
        return 1;
    }
 
    // 다음 노드 탐색하고 재귀로 넘긴다. 
    for (int i = 0; i < (*(node_arr[now_edge]->edge_vec)).size(); i++) {
 
        if (visited[(*(node_arr[now_edge]->edge_vec))[i]->end_node] == 0){
            visited[(*(node_arr[now_edge]->edge_vec))[i]->end_node] = 1;
            result += find_big_weight((*(node_arr[now_edge]->edge_vec))[i]->end_node,
                end_edge, min(weight, (*(node_arr[now_edge]->edge_vec))[i]->weight));
            visited[(*(node_arr[now_edge]->edge_vec))[i]->end_node] = 0;
        }
    }
 
    return result;
}
 
int main() {
    cin >> N >> M;
 
    // 0번은 사용하지 않고 버린다. 
    node_arr = (NODE**)malloc(sizeof(NODE*)*(N + 1));
 
    for (int i = 0; i <= N; i++) {
        node_arr[i] = (NODE*)malloc(sizeof(NODE));
        node_arr[i]->node_num = i;
        node_arr[i]->edge_vec = new vector<EDGE*>();
    }
 
    int sub_start, sub_end, sub_weight;
    // edge 받아서 연결 
    for (int i = 0; i < M; i++) {
        cin >> sub_start >> sub_end >> sub_weight;
        if (max_weight < sub_weight) max_weight = sub_weight; 
 
        // 동일한 놈이 없으면 추가해준다.  
        EDGE* sub_edge = (EDGE*)malloc(sizeof(EDGE));
        sub_edge->end_node = sub_end;
        sub_edge->weight = sub_weight;
        (*(node_arr[sub_start]->edge_vec)).push_back(sub_edge);
 
        sub_edge = (EDGE*)malloc(sizeof(EDGE));
        sub_edge->end_node = sub_start;
        sub_edge->weight = sub_weight;
        (*(node_arr[sub_end]->edge_vec)).push_back(sub_edge);
    }
 
    int factory_1, factory_2;
    cin >> factory_1 >> factory_2;
 
    find_big_weight(factory_1, factory_2, 987654321);
    cout << answer;
 
    return 0;
}
cs


사실 위에서 언급한 메모리 문제를 해결하다가 답을 못 찾아서, 다른 풀이를 보던 와중에 이진 탐색을 이용하는 것을 확인했다. 
이진 탐색을 이용하여 도로의 최대 무게값을 right로 지정하고 1을 left로 지정 하여 이진탐색을 수행한다.
left 와 right 의 중간값인 mid 값을 설정하고, dfs 함수에서 mid 값보다 작은 weight 를 가진 길이 나오면 바로 종료한다.  




(2) dfs 에서  이진 탐색을 적용하여 속도를 올린 풀이 

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream> 
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef struct EDGE {
    int end_node;
    int weight;
}EDGE;
 
typedef struct NODE {
    int node_num;
    vector<EDGE*>* edge_vec;
}NODE;
 
int N, M;
NODE** node_arr;
int visited[100001];
int answer = 0;
int max_weight = 0;
 
void visited_init() {
    for (int i = 0; i < 100001; i++)
        visited[i] = 0;
}
 
int find_big_weight(int now_edge, int end_edge, int weight, int depth, int min_weight) {
    //cout << "now_edge = " << now_edge << " , end_edge = " << end_edge << " , weight " << weight << ", depth="  << depth << "\n";
    
    int result = 0
    
    // 끝 노드이면 답에 추가 
    if (now_edge == end_edge) {
        if (answer < weight) answer = weight;
        return 1;
    }
 
    // 다음 노드 탐색하고 재귀로 넘긴다. 
    for (int i = 0; i < (*(node_arr[now_edge]->edge_vec)).size(); i++) {
 
        if (visited[(*(node_arr[now_edge]->edge_vec))[i]->end_node] == 0 &&
            (*(node_arr[now_edge]->edge_vec))[i]->weight >= min_weight) {
 
            visited[(*(node_arr[now_edge]->edge_vec))[i]->end_node] = 1;
            result += find_big_weight((*(node_arr[now_edge]->edge_vec))[i]->end_node,
                end_edge, min(weight, (*(node_arr[now_edge]->edge_vec))[i]->weight), depth + 1, min_weight);
        }
    }
 
    return result;
}
 
int main() {
    cin >> N >> M;
 
    // 0번은 사용하지 않고 버린다. 
    node_arr = (NODE**)malloc(sizeof(NODE*)*(N + 1));
 
 
    for (int i = 0; i <= N; i++) {
        node_arr[i] = (NODE*)malloc(sizeof(NODE));
        node_arr[i]->node_num = i;
        node_arr[i]->edge_vec = new vector<EDGE*>();
    }
 
    int sub_start, sub_end, sub_weight;
    // edge 받아서 연결 
    for (int i = 0; i < M; i++) {
        cin >> sub_start >> sub_end >> sub_weight;
        if (max_weight < sub_weight) max_weight = sub_weight; 
 
        // 동일한 놈이 없으면 추가해준다.  
        EDGE* sub_edge = (EDGE*)malloc(sizeof(EDGE));
        sub_edge->end_node = sub_end;
        sub_edge->weight = sub_weight;
        (*(node_arr[sub_start]->edge_vec)).push_back(sub_edge);
 
        sub_edge = (EDGE*)malloc(sizeof(EDGE));
        sub_edge->end_node = sub_start;
        sub_edge->weight = sub_weight;
        (*(node_arr[sub_end]->edge_vec)).push_back(sub_edge);
    }
 
    int factory_1, factory_2;
    cin >> factory_1 >> factory_2;
 
    int left, right;
    left = 1;
    right = max_weight;
 
    while (left <= right)
    {
        int mid = (right + left) / 2;
        visited[factory_1] = 1;
 
        if (find_big_weight(factory_1, factory_2, 9876543210, mid))
        { left = mid + 1; }
        else { right = mid - 1; }
 
        visited_init(); 
    }
    cout << answer;
 
    return 0;
}
cs


다른 풀이로는 bfs 를 이용한 풀이가 있다. 
다른 사람들의 풀이를 참고해 보면 좋을 듯 하다. 






▼댓글▼

▼추천 게시물▼