ํฐ์คํ ๋ฆฌ ๋ทฐ
[๋ฌธ์ ]
[ํ์ด]
์ด์คํ์ + BFS๋ฅผ ์ฌ์ฉํ๋ ๋ฌธ์ ๋ก ์๋์ ๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํ์์ต๋๋ค.
https://hidelookit.tistory.com/200
[๋ฐฑ์ค 1939] ์ค๋์ ํ (์๋ฐ)
๋ฐฑ์ค 1939๋ฒ ์ค๋์ ํ (์๋ฐ) ์ถ์ฒ www.acmicpc.net/problem/1939 1939๋ฒ: ์ค๋์ ํ ์ฒซ์งธ ์ค์ N, M(1≤M≤100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๋ค๋ฆฌ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ธ ์ ์ A, B(1≤A, B≤N), C(1≤..
hidelookit.tistory.com
left์ ์ต์๊ฐ 0์ ์ฝ์ ํฉ๋๋ค.
right ์ ๋ค๋ฆฌ๋ค์ค ๊ฐ์ฅ ์ค๋์ด ํฐ๊ฐ์ ๋ฃ์ด์ค๋๋ค.
(left + right)/2์ธ mid ๊ฐ๋ถํฐ ํด๋น ์ค๋์ ์ง์ผ๋ก ์ฌ-์ฌ์ ์ด๋ํ ์ ์๋์ง ํ์ธํ๋ฉฐ,
๋ง์ฝ ์ด๋ํ ์ ์๋ค๋ฉด mid+1, ์ด๋ํ ์์๋ค๋ฉด mid-1ํ๋ฉฐ ์ต๋ ์ค๋์ ์ฐพ์ต๋๋ค.
[์ฝ๋]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// ํ ๋ฒ์ ์ด๋์์ ์ฎ๊ธธ ์ ์๋ ๋ฌผํ๋ค์ ์ค๋์ ์ต๋๊ฐ
class Bridge{
int island;
int weight;
public Bridge(int island, int weight) {
this.island = island;
this.weight = weight;
}
}
public class Main {
public static int N;
public static int M;
public static ArrayList<ArrayList<Bridge>> bridge = new ArrayList<>();
public static int max = 0;
public static void main(String[] args) 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());
for(int i=0;i<=N;i++) {
bridge.add(new ArrayList<>());
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// ์๋ฑกํฅ์ด๋ผ 2๊ฐ ๋ฃ์ด์ค
bridge.get(a).add(new Bridge(b,c));
bridge.get(b).add(new Bridge(a,c));
if(max < c) {
max = c;
}
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int left = 0;
int right = max;
while(left <= right) {
int mid = (left + right)/2;
if(bfs(start,end,mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(right);
}
public static boolean bfs(int start, int end, int mid) {
boolean[] visit = new boolean[N+1];
Queue<Integer> q = new LinkedList<>();
q.add(start);
visit[start] = true;
while(!q.isEmpty()) {
int p = q.poll();
if(p == end) {
return true;
}
for(Bridge i: bridge.get(p)) {
if(!visit[i.island] && mid <= i.weight) {
visit[i.island] = true;
q.add(i.island);
}
}
}
return false;
}
}
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] ๋ฐฑ์ค 9466๋ฒ - ํ ํ๋ก์ ํธ (0) | 2022.06.28 |
---|---|
[Java] ๋ฐฑ์ค 14888๋ฒ - ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ (0) | 2022.06.28 |
[Java] ๋ฐฑ์ค 1931๋ฒ - ํ์์ค ๋ฐฐ์ (0) | 2022.06.13 |
[Java] ๋ฐฑ์ค 2461๋ฒ - ๋ํ ์ ์ (0) | 2022.06.05 |
[Java] ๋ฐฑ์ค 2564๋ฒ - ๊ฒฝ๋น์ (0) | 2022.06.05 |
- Total
- Today
- Yesterday
- git
- ํฌํฌ์ธํฐ
- 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด
- ๋ชจ๋ ์๋ฐ์คํฌ๋ฆฝํธ deep dive
- Baekjoon
- TDD
- ๋ฐฑ์ค node.js
- ๊ฐ์ฒด์งํฅ ํ๋ก๊ทธ๋๋ฐ
- ํ๋กํ ์ฝ
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- JavaScript
- ๋ฐฑ์ค
- ์๋ฐ
- http
- ์ด๋ถํ์
- ๋ ์์ปฌ ํ๊ฒฝ
- ๋คํธ์ํฌ
- ์ฝ๋ฉํ ์คํธ
- fp
- ํจ์ํ ํ๋ก๊ทธ๋๋ฐ
- ์ด์์ฒด์
- ํ๋ก๊ทธ๋๋จธ์ค
- map
- ์๊ณ ๋ฆฌ์ฆ
- ์ ์ญ ๋ณ์
- ํ๋กํผํฐ
- ์นด์นด์ค ์ธํด
- ๋์์ธ ํจํด
- ์๋ฐ์คํฌ๋ฆฝํธ
- ๋ฐฑ์ค javascript
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |