ํฐ์คํ ๋ฆฌ ๋ทฐ
[๋ฌธ์ ]
[ํ์ด]
์ด์คํ์ + BFS๋ฅผ ์ฌ์ฉํ๋ ๋ฌธ์ ๋ก ์๋์ ๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํ์์ต๋๋ค.
https://hidelookit.tistory.com/200
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
๋งํฌ
TAG
- JavaScript
- http
- ํ๋กํ ์ฝ
- ๋์์ธ ํจํด
- ํฌํฌ์ธํฐ
- ์ ์ญ ๋ณ์
- ์ด๋ถํ์
- ๋คํธ์ํฌ
- TDD
- fp
- ์ฝ๋ฉํ ์คํธ
- ๋ ์์ปฌ ํ๊ฒฝ
- ๊ฐ์ฒด์งํฅ ํ๋ก๊ทธ๋๋ฐ
- ํ๋ก๊ทธ๋๋จธ์ค
- map
- ์๋ฐ
- ํ๋กํผํฐ
- ๋ฐฑ์ค
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- ํจ์ํ ํ๋ก๊ทธ๋๋ฐ
- ๋ฐฑ์ค javascript
- ๋ชจ๋ ์๋ฐ์คํฌ๋ฆฝํธ deep dive
- 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด
- ์๊ณ ๋ฆฌ์ฆ
- ์๋ฐ์คํฌ๋ฆฝํธ
- ๋ฐฑ์ค node.js
- git
- ์นด์นด์ค ์ธํด
- ์ด์์ฒด์
- Baekjoon
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
๊ธ ๋ณด๊ดํจ