- N개의 섬이 존재. 이들 중 "몇 개의 섬 사이에 다리"가 설치되어있다.
- "두 개의 섬"에 공장을 세워 두고, 물품을 생산하는 일을 한다.
- a공장에서 b공장으로 물품 수송할 일이 생기곤 한다.
- 다리마다 중량제한이 있어, 무턱대고 물품을 옮길 수 없다. 만약 중량제한 초과하는 물품이 다리를 지나게 되면 다리가 무너지게 된다.
- 구해야 할 것
- 한 번의 이동에서, 옮길 수 있는 물품들의 중량의 최댓값 구하기
- 주어지는 것
- 섬의 개수 N이 주어진다.
- 다리의 개수 M개가 주어진다.
- 각 다리에 대한 정보 (a,b,c) 가 주어진다. a섬과 b섬을 연결하며 중량제한이 c인 다리를 의미한다.
- 서로 같은 두 도시 사이 여러 개의 다리가 있을 수도 있으며💥💥💥 모든 다리는 "양방향"이다.
- 마지막 줄에는 공장이 위치해 있는 서로 다른 두 정수가 주어진다.
- 공장이 있는 두 섬을 연결하는 경로는, 항상 존재하는 데이터만 입력으로 주어진다.
- 문제 이해하기
- 노드의 개수가 10000개 이기 때문에 adjacent matrix는 사용할 수 없을 것 같아 adjacent list를 사용하려 한다.
- 문제 풀이
- N은 최대 10000개이고, M은 최대 10만개이다. 또한 각 중량은 최대 10억을 갖는다.
- 무조건 a에서 b로 갈 수 있는 경로를 찾을 수 있어야 하기 때문에, 자칫 dfs를 사용해서는 시간초과가 생길 수 있을 듯하다.
- bfs를 사용한다면, Queue에 넣는 정보는 (최소 브릿지 중량, 노드)
- 이미 방문했던 노드를 Queue에서 빼게 되는 경우, 만약 그것의 최소브릿지 중량이 더 작다면, .. 음 이거를 처리하지 않으면 또 안됨.. 그러면 결국 visit되었던 것도 또 다시 똑같은 경로 다 확인하고 그렇게 됨
- 그리고 bfs를 사용하면 Queue에다가 1만개의 노드를 모두 넣게 되는 상황까지도 올 수가 있다는 것. 이 경우 메모리초과 위험이 있다.
- 흠.. ajd list를 만들 때, 아예 Sorting한다면? 그런데 노드의 개수가 1만개라는.. 그리고 총 간선의 정보가 100만개가 주어질 수 있어서.
다른 사람의 풀이를 검색했다
내가 사로 잡혀 있던 것
- 나는 , 두 섬을 이을 수 있는 경로 중에서, 가장 작은 비용을 가진 브릿지가 최대값을 갖는 경로를 찾아야 한다 생각했다.
- 그래서 각 경로를 다 해보면서 , 최소 브릿지의 최댓값을 update해 가야한다고 생각이 사로잡혀 있었다.
- 💥처음부터 아예 제한중량에 초점을 맞추고 제한중량을 선택하여, 이 제한중량으로 두 섬을 이을 수 있는가에 초점을 잡아야 했다. 💥
다른 사람의 풀이를 보고
힌트를 얻기 위해 검색했다.
-
BFS와 이진탐색을 함께 사용해야 한다는 내용을 보았다.
-
BFS와 이진탐색을 어떻게? —>
- 모든 중량제한을 받으며 그래프를 생성함과 동시에, MAX 중량제한 값을 업데이트 해 나간다.
- left = 0, right = MAX 로 하여, mid값을 중량제한으로 하여, bfs를 실행한다
- bfs를 통해서 목표 공장에 도달 시 —>
- max_limit을 업데이트한다.
- 중량을 최대한으로 늘려봐야 하기 때문에 left = mid+1로 설정한다.
- bfs를 통해서 목표 공장에 도달 전에 실패 할 경우 —> 중량 제한을 더 늘려야 한다 : left = mid +1로 설정한다.
- bfs를 통해서 목표 공장에 도달 시 —>
- 즉, 중량제한을 이진탐색으로 설정해 가며, bfs로 조건을 만족할 수 있는지를 통하여 문제를 풀 수 있게 된다.
- 최대 중량 제한을 이진탐색으로 먼저 설정하고, bfs를 이용해서 해당 중량 제한 안에서 목표지점까지 도달이 가능하다면, 해당 값으로는 충분히 가능함을 의미 —> 최대 중량 제한을 늘린다.
- But, 목표지점까디 도달이 불가능하다면, 해당 값으로는 불가능함을 의미하므로 이진탐색을 통해 , 최대중량을 줄여 시도한다.
-
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ public static int n,m; public static int start,end; public static ArrayList<int[]>[] graph; public static boolean[] visit; public static int max=0; // 입력받은 중량 중 최대 중량 public static int ans=1; // 성공가능 중량 중 최대 중량 public static void Setting() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); graph = new ArrayList[n+1]; visit = new boolean[n+1]; int i=0; for(i=0;i<n;i++){ graph[i]= new ArrayList<>(); } for(i=0;i<m;i++){ st = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st.nextToken())-1; int v2 = Integer.parseInt(st.nextToken())-1; int w = Integer.parseInt(st.nextToken()); graph[v1].add(new int[]{v2,w}); graph[v2].add(new int[]{v1,w}); if(w>max) max = w; } st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken())-1; end = Integer.parseInt(st.nextToken())-1; } // 0 1 public static void binSearch(int left,int right){ int mid =0; while(left<=right){ mid = (left+right)/2; if(bfs(mid)){ ans = mid; left = mid+1; }else{ right = mid-1; } } } // 하나라도 성공시 true // 실패시 false public static boolean bfs(int limit){ Queue<Integer> q = new LinkedList<>(); Arrays.fill(visit,false); q.add(start); visit[start]=true; while(q.isEmpty()==false){ int cur = q.poll(); if(cur==end){ return true; } for(int i=0;i<graph[cur].size();i++){ int[] next = graph[cur].get(i); if(visit[next[0]]) continue; if(next[1]<limit) continue; q.add(next[0]); visit[next[0]] = true; } } return false; } public static void main(String[] args) throws IOException{ Setting(); binSearch(0,max); System.out.println(ans); } }
또 다른 방법 : 크루스칼 알고리즘
- 갑자기, 이 문제를 다시 한 번 풀어보려고 문제를 봤을 때는, 크루스칼 알고리즘이 먼저 떠올랐었다. ( 또다시 이진탐색 은 생각나지 않았다 ㅋㅋㅋ... 그래도 크루스칼 알고리즘으로 풀렸으니 반타는 친 것 같다)
- 브릿지들 정보들을 받았으니, 이들을 Decreasing으로 sorting을 한다.
- 여기에 Priority Queue를 사용했다.
- 참고로, 이 문제의 edge들은 "양방향" 이기 때문에, 이런 크루스칼 알고리즘이 가능하다.
- 같은 vetex 사이 여러개의 edge가 있어도 상관 없다. 무조건 그 중 "최대중량" 가진 edge만을 사용하게 된다. ( Priority Queue에서 순차적으로 edge정보를 꺼내어, 이미 같은 graph 소속인 vetex 사이 edge 정보인 경우는 뛰어넘게 되기 때문이다. 이미 연결되었었다는 것은, 이미 PQ에서 나왔던 edge를 사용했다는 것이고, 이 edge의 중량이 더 컸었음을 의미한다. )
- 기존에 봤던 크루스칼 알고리즘은, 원래 Increasing으로 sorting해서, 여기서 edge들을 순서대로 하나씩 뽑아서, 이미 그래프로 연결되어 있는 edge라면 pass하는식으로 진행했다. (가장 큰 중량으로 잇는 것이 이 문제의 목표이기 때문이다)
- 따라서 여기엔 Union Find도 쓰였다.
- find 함수를 개선한 Union find를 사용한다면, 최악의 경우 O(v)임 (그런데 어차피, sort에는 O(eloge)이 사용된다. (v는 vertex의 개수, e는 edge의 개수 )
- 문제는...
- PQ에서 edge를 하나씩 빼서, 연결(union)할 때 마다, 두 공장이 같은 그래프에 속하게 된 것인지를 확인해야한다.
- 브릿지들 정보들을 받았으니, 이들을 Decreasing으로 sorting을 한다.
- 약간의 시간이라도 줄여보기 위해 이렇게 했다.
- union 할 때에도, 기존에 a,b가 같은 그래프 소속이었다면 return true를 하고, 그 전엔 같은 그래프 소속이 아니었고, 여기서 union 해줄 때는 return false를 리턴해준다.
- 굳이 union할 때도 이런식으로 boolean을 return해, 확인 해 준 것은, 이미 이전에 union 함수를 통해 두 노드가 같은 그래프에 속하게 되었을 때, start,end가 같은 그래프인지 확인하는 과정을 거쳤었을 것이기 때문이다.
- 즉, 둘의 union이 새롭게 일어난 것도 아닌데, 무의미하게 start,end가 같은 그래프인지 확인하는 로직을 중복 실행하지 않기 위함이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class main {
public static int n, m; // n 은 vertex 개수, m은 edge 개수
public static int start, end; // 연결되어야 하는 두 공장
public static int[] root;
public static int max = 0; // 입력받은 중량 중 최대 중량
public static Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[2] - o1[2];
}
});
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
// root table init
root = new int[n];
for(int i=0;i<n;i++)
root[i]=i;
// edge info
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken()) - 1;
int v2 = Integer.parseInt(st.nextToken()) - 1;
int w = Integer.parseInt(st.nextToken());
pq.add(new int[]{v1,v2,w});
}
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken()) - 1;
end = Integer.parseInt(st.nextToken()) - 1;
}
public static void solve(){
while(pq.isEmpty()==false) {
// edge extract
int[] cur = pq.poll();
// two nodes connected by this edge to be checked if they already belong to the same graph
if (union(cur[0], cur[1]) == true) continue;
// 새로 union 시켜 줄 때(기존에 두 노드가 같은 그래프가 아니었던 경우) 마다, start,end가 같은 그래프 소속이 되었는지 확인
// 같은 그래프 소속이라면, 최대 중량을 찾은 것 --> 종료
if (sameGraph(start, end) == false) continue;
max = cur[2];
break;
}
}
// a가 속한 그래프의 root
// 좀 더 개선한 find --> 다음에 a--root까지 의 path에 있는 상위 intermediate node들에 대한 find 속도가 개선된다.
public static int find(int a){
if(root[a]==a)return a;
return root[a]= find(root[a]);
}
// a,b가 이미 같은 그래프 소속 --> return true;
// 다른 소속 --> union 시켜주고, 이전에는 같은 그래프 아니었으니 false.
public static boolean union(int a,int b){
int ra = find(a);
int rb = find(b);
if(ra==rb) return true;
else if(ra<rb) root[ra]=rb;
else root[rb]=ra;
return false;
}
public static boolean sameGraph(int a, int b){
int ra = find(a);
int rb = find(b);
if(ra==rb) return true;
else return false;
}
public static void main(String[] args) throws IOException {
Setting();
solve();
System.out.println(max);
}
}첫 번째 풀이보다 효율은 더 좋게 나왔다.
