문제

https://www.acmicpc.net/problem/1939

소스코드

MAIN

    private static int n,m;
    private static ArrayList<ArrayList<Island>> list = new ArrayList<>();
    private static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        int left = 0;
        int right = 0;

        for (int i=0; i<=n; i++) {
            list.add(new ArrayList<>());
        }
        //n 갯수 만큼 리스트 생성

        int max = 0;

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(reader.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Island(b,c));
            list.get(b).add(new Island(a,c));
			// 그래프 만들어주기 
            
            max = Math.max(max, c);
            //가중치 max
        }

        right = max;

        st = new StringTokenizer(reader.readLine());

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        while (left <= right) {

            int mid = (left+right)/2;
            visit = new boolean[n+1];
			// 방문여부 체크를 위한 배열
            if (bfs(start,end,mid)) {
            // 다리를 건넜을 때
                left = mid+1;
            } else {
            //건너지 못했을 때 
                right = mid-1;
            }

        }//while

        System.out.println(right);


    }

BFS

private static boolean bfs(int start, int end, int mid) {

        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start] = true;

        while (!q.isEmpty()) {

            int island = q.poll();

            if (island == end) {
                return true;
            }
            

            for (Island i : list.get(island)) {

                if (!visit[i.destination] && mid <= i.cost) {
                    //가중치가 mid보다 클때 , 방문 안했고 
                    visit[i.destination] = true;
                    q.add(i.destination);
                }

            }

        }//while

        return false;

    }//bfs

Node

static class Island {
        int destination, cost;

        Island (int destination, int cost) {
            this.destination = destination;
            this.cost = cost;
        }
    }

풀이방법

  1.  ArrayList[n + 1] 로 Graph 생성 및 입력 값 받기

  2.  low(left) 를 1로, high(right) 를 다리들 중 최대 중량으로 설정.

  3.  이진탐색 while문 반복

  4.  BFS 방식을 통해 poll한 공장에 연결된 접점의 공장들을 Queue에 담아가며, B공장에 도착할 때 까지 반복

  5.  4번 방식을 진행하면서 간선(다리)들의 무게 중량과 mid(선택한 이동 가능 중량) 값을 비교한다.

    -> mid 값보다 큰 경우 : 해당 공장을 기준으로 4번 이어서 진행. (다음 경로를 탐색)

    -> mid 값보다 작은 경우 : False. 다리를 건너지 못하므로 해당 경로로 탐색 종료. 그냥 다음 원소를 큐에서 poll한다.

  6.  목적지 공장(B공장)에 하나라도 도착하거나 하나라도 도착하지 못하면 BFS를 종료한다.

    그 후, 하나라도 도착한 경우 -> 별도로 mid 값 저장해서 최댓값 찾기. 다음에 윗 배열 탐색(low = mid + 1)

            하나라도 도착하지 못한 경우 ->다음에 아래 배열 탐색(high = mid - 1)
 
  7.  그래서 B공장에 도착한 것들 중 최댓값을 출력하면 끝.

참고

https://maivve.tistory.com/144
https://velog.io/@phc09188/08.10-%EB%B0%B1%EC%A4%80-1939