<Algorithm> 175. 중량제한(BJO)

1. 1939번 중량제한(BJO)

   사용 알고리즘 :  BFS, 이분탐색

• 요즘 이분탐색 카테고리 문제를 풀고있어 이 문제를 봤을때 카테고리 모르고 봤을때 이분탐색을 생각할 수 있을까라는 생각이 들었다. 

• 문제만 보면 그래프 느낌이 들었고 왜 이분탐색일까라는 생각이 많이 들었다.

• 그 이유가 https://www.acmicpc.net/board/view/33835 여기에 잘 나와있었다.

• 오래걸린 이유가 지점에서 다른지점으로 가는데 경로가 여러개 일 수 있다는 조건 때문에 할때마다 정렬하니 메모리초과가 발생했다...

• 이분탐색으로 푼다면 어떤 경로를 사용하든 통과만 하면되는 것이 이 문제의 핵심인 것 같다.

문제에 대한 접근&생각

1. a지점에서 b지점까지 운반해야함 -> BFS!
2. 옮길 수 있는 최대 무게를 구해야함(운반 거리는 상관없음) -> 이분탐색!

내 코드 

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.stream.Collectors; public class Main {     static int n,m;     static List<Island>[] map;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         m = sc.nextInt();         map = new ArrayList[n];         /****************************          * 최대중량을 기준으로 이분탐색을 하여          * 그 무게가 도달할 수 있는 지 판단한다.          * 이때 가장 무게가 나가는 것을 출력한다.          ****************************/         for(int i = 0; i < n; i++)              map[i] = new ArrayList<>();         long max = 0;         for(int i = 0; i < m ; i++) {             int a = sc.nextInt()-1;             int b = sc.nextInt()-1;             long c = sc.nextLong();              map[a].add(new Island(b, c));              map[b].add(new Island(a, c));              max = Math.max(c, max);         }         int a = sc.nextInt()-1;         int b = sc.nextInt()-1;         long start = 0;         long end = max+1;         long ans = 0;         while (start < end) {             long mid = (start+end)/2;             if(bfs(mid, a, b)) {                 ans = Math.max(ans, mid);                 start = mid+1;             }else {                 end= mid;             }         }         System.out.println(ans);     }     private static boolean bfs(long mid,int a, int b) {         boolean[] visited = new boolean[n];         Queue<Integer> queue = new LinkedList<>();         queue.add(a);         visited[a] = true;         while(!queue.isEmpty()) {             int v = queue.remove();             for(Island island : map[v]) {                 if(!visited[island.num] && mid <= island.dist) {                     visited[island.num] = true;                     if(island.num == b) return true;                     queue.add(island.num);                 }             }         }         return false;     }     static class Island{         int num;         long dist;         public Island(int num, long dist) {             this.num = num;             this.dist = dist;         }     } }   Colored by Color Scripter

cs

 

얻은 것

• BFS는 방문한 노드를 중첩으로 큐에 넣지 않는다!