7/26 연습

2017. 7. 27. 18:51알고리즘 문풀/BOJ 연습

#1. 중량제한


문제 : icpc.me/1939


굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다.


1. BFS


물건을 보내는 공장을 \(s\), 받는 공장을 \(t\)라고 하자.

또 각각의 정점까지 수송할 수 있는 최대의 비용을 \(F[v]\)라고 하자.

(정점 \(v\), c=\(s\)에서 \(v\)까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 \(Q\)를 잡고, \(Q\)에 \((s,F[s]\leftarrow \infty)\)를 넣으면서 BFS 개시.


\(Q\)가 빌 때까지, \(Q\)의 front \(k\)에 대해서 \(k.v\)에 연결되어 있는 점 \(u\)들을 보는데, \(min(k.c,bridge\_capacity[v\to u])\)가 기존의 \(F[u]\)보다 크다면 이 값으로 \(F[u]\)를 갱신해주고, \(u,F[u]\)를 \(Q\)에 넣으면 된다. 원하는 답은 \(F[t]\).


Time Complexity : \(O(BFS)=O(V+E)\)


2. Kruskal Algorithm


문제를 잘 들여다보면, 결국 Minimum Spanning Tree에서 \(s\to t\)의 경로 상에서 bridge_capacity의 최댓값을 찾는 문제가 됨을 알 수 있다.


크루스칼 알고리즘을 돌릴 때처럼, 모든 에지를 bridge_capacity가 큰 순서대로 정렬하자. Union-Find를 이용하여 계속 점을 이어주면서, 어떤 에지 \(e\)를 추가했을 때 \(s\)와 \(t\)가 이어지면 \(bridge\_capacity[e]\)를 출력하면 된다.


Time Complexity : \(O(E lg E + E\alpha (V)) = O(E lg E)\)

얘가 왜 더 빠른지는 모르겠다. 입출력을 다르게 해서 그런가...




#2. 운동


문제 : icpc.me/1956


Floyd_Warshall 알고리즘으로 빠르게 답을 찾을 수 있다. 정점 \(u\)에서 \(v\)로 가는 최단경로의 길이를 \(sp[u][v]\)라고 하면, \(sp[u][u]\)의 최솟값을 출력하면 된다.


Time Complexity : \(O(V^3)\)



'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

7/30 ~ 7/31 연습  (0) 2017.08.01
7/29 연습  (0) 2017.07.30
7/27~7/28 연습  (0) 2017.07.29
7/26 연습  (0) 2017.07.27
7/25 연습  (0) 2017.07.26
7/24 연습  (0) 2017.07.25