반응형
https://www.acmicpc.net/problem/1939
🔶 풀이
한 번의 이동에서 옮길 수 있는 물품들의 최대값을 구하시오.
가능한 최대 중량을 찾기 위해서는 bfs로만 풀 수 없고, 이진 탐색을 이용해야한다.
1. 입력하는 과정에서 min, max 값을 선언해주고, 다리는 양방향이므로 arrList에 두 번씩 입력해준다.
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
max = Math.max(max, v);
min = Math.min(min, v);
arrList[s].add(new Bridge(e, v));
arrList[e].add(new Bridge(s, v));
}
2. 모든 입력을 완료했으면 min, max 값으로 이진 탐색을 진행한다.
: 중량(mid)를 기준으로 해당 경로를 이용할 수 있는지 여부를 따지면서 진행하면 된다.
이동할 수 없음 → 중량이 너무 크다는 뜻이므로 max - 1
이동할 수 있음 → 중량이 너무 작다는 뜻이므로 min + 1, 또한 이동할 수 있는 값이므로 ans 초기화
3. 해당 경로를 이용할 수 있는지 여부는 bfs로 진행한다.
: 해당 경로를 안전하게 이용할 수 있다면 true를 반환해주고, 그렇지 않다면 false를 반환해준다.
// 현재 섬에서 갈 수 있는 섬 개수만큼
for (int i=0; i<arrList[now].size(); i++) {
// 다리를 건널 수 있고, 도착 섬에 방문하지 않은 경우
if (arrList[now].get(i).weight >= w && !visited[arrList[now].get(i).endLand]) {
visited[arrList[now].get(i).endLand] = true;
q.add(arrList[now].get(i).endLand);
}
}
재방문 방지를 위해서 visited[] 배열도 선언해주어야함.
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Bridge>[] arrList; // 다리 정보를 담는 배열
static int N, M;
public static class Bridge {
int endLand, weight;
public Bridge(int endland, int weight) {
this.endLand = endland;
this.weight = weight;
}
}
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()); // 다리에 대한 정보
arrList = new ArrayList[N+1];
for (int i=0; i<=N; i++) {
arrList[i] = new ArrayList<>();
}
int max = 0;
int min = Integer.MAX_VALUE;
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
max = Math.max(max, v);
min = Math.min(min, v);
arrList[s].add(new Bridge(e, v));
arrList[e].add(new Bridge(s, v));
}
st = new StringTokenizer(br.readLine());
int sLand = Integer.parseInt(st.nextToken()); // 출발 섬
int eLand = Integer.parseInt(st.nextToken()); // 도착 섬
int ans = 0;
while (max >= min) {
int mid = (max + min) / 2; // 현재 중량
// 현재 중량(mid)로 출발 섬에서 도착 섬으로 갈 수 있는지 여부
if (canGo(sLand, eLand, mid)) {
min = mid + 1;
ans = mid;
} else {
max = mid - 1;
}
}
System.out.println(ans);
}
/**
*
* @param s 출발 섬
* @param e 도착 섬
* @param w 현재 중량
* @return
*/
public static boolean canGo(int s, int e, int w) {
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[N+1];
q.add(s);
visited[s] = true;
while (!q.isEmpty()) {
int now = q.poll();
// 도착할 경우
if (now == e) {
return true;
}
// 현재 섬에서 갈 수 있는 섬 개수만큼
for (int i=0; i<arrList[now].size(); i++) {
// 다리를 건널 수 있고, 도착 섬에 방문하지 않은 경우
if (arrList[now].get(i).weight >= w && !visited[arrList[now].get(i).endLand]) {
visited[arrList[now].get(i).endLand] = true;
q.add(arrList[now].get(i).endLand);
}
}
}
return false;
}
}
반응형
'알고리즘 > 이분 탐색' 카테고리의 다른 글
[자바로 푸는 백준] 17266번 어두운 굴다리 (0) | 2023.06.15 |
---|---|
[백준]JAVA - 2110번: 공유기 설치 (0) | 2022.10.24 |
[백준]JAVA - 1654번: 랜선 자르기 (0) | 2022.09.21 |