문제
여러 섬과 중량제한이 있는 다리가 주어질 때
공장이 있는 한 섬에서, 다른 공장이 있는 섬으로 옮길 수 있는 물품들의 최대 중량을 구하시오
생각
공장이 있는 한 섬을 시작점으로 다른 공장이 있는 섬까지 탐색한다
시간복잡도
그래프 문제는 시간복잡도 알아내기 어려우니까 최악의 경우로 시간복잡도를 생각해보쟈
섬이 최대 10,000개, 다리가 최대 100,000개
섬이 1자로 쭉 배치되어있고, 공장은 섬 끝과 끝에 있고,
섬 사이사이가 10개의 다리가 있다고 치면
섬을 건너갈 때마다 10가지 경우가 있으니까
10^10000 오 아주 큼
흠 그래서 그냥 다 돌아보고 최대 중량을 구하는건 안 되는건 알겠음
시간초과 아이디어
그래서 나는 생각했다
현재까지 방문한 경로가 가능한 최대 중량은 지나온 다리들의 제일 낮은 중량제한 임
탐색을 하면서 어느 섬을 지나갈 때 가능한 최대 중량을 저장해놓고,
만약 이미 방문했던 섬에 다른 경로로 방문을 하게 된다면
그전에 방문했던 중량보다 더 큰 중량으로 오는 경우에만 더 탐색을 하게 했다
더 작은 중량은 지나가봤자 정답이 될 수는 없구,
같은 크기의 중량은 중복 탐색이니까~!~~!
으음 이렇게 처리를 해주면 시간 초과가 안나겠지(두근두근)
마음으로 구현했는데 시간 초과임
아래와 같은 방법으로 구현했음
//큐에 공장이 있는 한 섬(i1)을 넣어놓음
while (!q.empty()){
int nownode = q.front().first;
int nowweight = q.front().second;
q.pop();
//이미 다른 공장 섬(i2)에 도착했다면, 그 중량보다 큰 애들만 탐색하쟈
if (nowweight <= check[i2]) {
continue;
}
for (int i = 0; i < info[nownode].size(); i++) {
int nextnode = info[nownode][i].first;
int nextweight = info[nownode][i].second;
//가능한 최대 중량은 지나온 다리들 중 제일 낮은 중량제한만큼
nextweight = nowweight < nextweight ? nowweight : nextweight;
//가봤자인 애들은 더 탐색 안 할랭
if (nextweight <= check[i2] || check[nownode] == check[nextnode]) {
continue;
}
//그전에 방문했던 중량보다 더 큰 중량으로 오는 경우에만 더 탐색
if (check[nextnode] < nextweight) {
check[nextnode] = nextweight;
if (nextnode != i2) {
q.push(make_pair(nextnode, nextweight));
}
}
}
}두뇌 풀가동
흐음 멋진 알고리즘이라 생각했지만, 시간초과.
무엇이 이렇게 오랜 시간을 걸리게 하는 걸까 고민해보았다
옆에서 최악의 경우를 생각해보라길래 생각해보니
흐음~ 그전에 지나간 경로보다 좋으면 지나가라 라는게
운 나쁘게도, 가능한 최고 중량이 작은 애들이 먼저 탐색되어서
내가 이렇게 if 처리를 절라리 해줘도 다 지나가는 경우가 있다는 걸 알게됌
(한 섬을 최고 중량 2로 지나가고 3으로 지나가고 4로 지나가고.. 9로 지나가고 ..)
호오~ 그것 참 슬픈일이야
난 이 알고리즘을 포기할 수 없어서 더 생각해보니
그럼 큰 애들이 먼저 지나가면 작은 애들은 못 지나갈 거 아냐?
(9가 지나가면 2도 3도 4도 .. 다들 못 지나가고 탐색 끝!)
그래서 우선 순위 큐를 써서 가능한 최대 중량이 큰 경로를 먼저 탐색하도록 했다
그랬더니~~!~ 맞았습니다ㅎㅔ헤헤
+내가 이런 방법은 뭐냐구 물어보니까 bfs/dfs 같은 방법은 아니랬다.. 프림도 아니구..
그냥 우선순위 큐를 쓴 그래프 탐색.. 이라고 하래
++우선순위 큐가 push할 때 시간복잡도가 O(logN)니까
뭐 위에서 설명한 최악의 경우에선 O(logNM) 정도 되는건가..?
좀 더 시간 줄일 수는 있을까?
Q 흐음 근데 위와 같은 알고리즘이라면
그냥 맨 처음 다른 공장에 도착하면 그게 최대값 아닐까?
A i1에서 시작해서 바로 i2에 도착하면 반환하게도 해봤다
//새로운 섬을 탐색할 때 i2면 바로 출력하고 끝내~~
if (nextnode != i2) {
q.push(make_pair(nextweight, nextnode));
}
else {
cout << check[i2];
return 0;
}오 틀렸습니다!
Q 생각해보니까 제일 큰 걸로 오긴 왔는데 마지막 탐색 때
낮은 다리로 와서 최대 중량이 엄청 작아지는 문제가 있넹!
A 그럼 i2에 도착했을 때 현재 보고있는 최대 가능한 중량이 a라면
큐에 남아있는 애들 중에 a인 애들만 탐색하도록 할까?
오~ a가 아닌 애들 중에서도 답이 될 수도 있었다~!~
더 나대지 않기로 생각했다ㅎㅎ
다른 사람들 알고리즘
보통은 이분탐색을 써서 0에서 1,000,000,000 사이값으로 중량 선택 후
BFS는 공장에서 공장으로 이 중량으로 지나갈 수 있을까?
방법으로 문제를 풀더라
이분탐색은 O(logN) 이니까 C가 커두 빠르니까
중량으로 못 가면 바로 멈추고, 도착해도 바로 멈추고
아주 빠르게 문제를 해결할 수 있다구 한당
이분 탐색도 마음에 담아두쟈!
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, i1, i2;
int a, b, c;
int check[10005];
vector<pair<int, int>> info[10005];
priority_queue<pair<int, int>> q;
pair<int, int> tempq;
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
info[a].push_back(make_pair(c, b));
info[b].push_back(make_pair(c, a));
}
cin >> i1 >> i2;
check[i1] = 1000000005;
q.push(make_pair(1000000005, i1));
while (!q.empty()) {
int nowweight = q.top().first;
int nownode = q.top().second;
q.pop();
if (nowweight <= check[i2]) {
continue;
}
for (int i = 0; i < info[nownode].size(); i++) {
int nextweight = info[nownode][i].first;
int nextnode = info[nownode][i].second;
nextweight = nowweight < nextweight ? nowweight : nextweight;
if (nextweight <= check[i2] || check[nownode] == check[nextnode]) {
continue;
}
if (check[nextnode] < nextweight) {
check[nextnode] = nextweight;
if (nextnode != i2) {
q.push(make_pair(nextweight, nextnode));
}
}
}
}
cout << check[i2];
return 0;
}