출처 : https://www.acmicpc.net/problem/1939
중량제한 성공 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 4891 | 1225 | 756 | 24.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, 987654321, 0, mid)) { left = mid + 1; } else { right = mid - 1; } visited_init(); } cout << answer; return 0; } | cs |
다른 풀이로는 bfs 를 이용한 풀이가 있다.
다른 사람들의 풀이를 참고해 보면 좋을 듯 하다.