문제 1939번

전체코드

import java.io.*;
import java.util.*;
class island{
    int next;
    int weight;
    public island( int next, int weight){
        this.next = next;
        this.weight = weight;
    }
}
public class boj1939 {
    static int N,M, result;
    static List<island>[] list;
    static boolean[] visited;
    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());
        list = new ArrayList[N+1];
        for (int i = 1; i < N+1; i++) {
            list[i] = new ArrayList<>();
        }
        int left = Integer.MAX_VALUE; int right = 0;
        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());
            list[a].add(new island(b,c)); list[b].add(new island(a,c));
            left = Math.min(left, c);
            right = Math.max(right, c);
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); int finish = Integer.parseInt(st.nextToken());
        while(left  <= right){
            visited = new boolean[N+1];
            int mid = (left + right)/2;
            if(bfs(mid, start, finish)){
                left = mid +1;
            }
            else right = mid -1;
        }
        System.out.println(right);
    }
    public static boolean bfs(int mid, int start, int finish){
        Queue<Integer> qu = new LinkedList<>();
        qu.offer(start);
        visited[start] = true;
        while(!qu.isEmpty()){
            int temp = qu.poll();
            if(temp == finish) return true;
            for (int i = 0; i < list[temp].size(); i++) {
                if(list[temp].get(i).weight >= mid && visited[list[temp].get(i).next] == false){
                    visited[list[temp].get(i).next] = true;
                    qu.offer(list[temp].get(i).next);
                }
            }
        }
        return false;
    }
}

풀이 접근

• 한 섬에 다리가 없을 수도 있고, 여러개가 있을 수도 있다. 그래서 전체 탐색을 하기 위해 브루트포스 탐색 방법을 사용하기로 했다.
  그냥 start지점 부터 따라다니면서 finish 지점까지의 max 값을 찾는 방식으로 코드를 구현하면 길이 끊어져 있는 경우 혹은 목표 지점까지 갈 수 없는 경우에 예외가 발생할 것 같아 무게에 대한 이분탐색으로 bfs or dfs를 사용하기로 하자.

1. 2차원 list로 출발지에 대한 list를 만들고, 안에는 island(연결된 섬, 무게) class 형태로 만든다.
2. 다리의 정보를 받을 때 이분탐색을 위한 left와 right는 Math의 메소드들로 찾아주고, list[start]와 list[finish]에 연결 된 섬과 다리의 무게 정보를 저장한다.
3. bfs or dfs를 통해 true를 반환한 경우 최대값이 더 있을 수 있으므로 left =mid+1
   false를 반환한 경우 right = mid-1로 이분탐색을 진행한다.
4. 탐색이 끝나고 나온 결과값 right를 출력한다.

dfs와 bfs

dfs

public static void dfs(int start, int finish, int limitweight){
        if(start == finish){
            result = start;
            return;
        }
        visited[start] = true;
        for(island i : list[start]){
            if(!visited[i.next] && limitweight<= i.weight){
                dfs(i.next, finish, limitweight);
            }
        }
    }

bfs

public static boolean bfs(int mid, int start, int finish){
        Queue<Integer> qu = new LinkedList<>();
        qu.offer(start);
        visited[start] = true;
        while(!qu.isEmpty()){
            int temp = qu.poll();
            if(temp == finish) return true;
            for (int i = 0; i < list[temp].size(); i++) {
                if(list[temp].get(i).weight >= mid && visited[list[temp].get(i).next] == false){
                    visited[list[temp].get(i).next] = true;
                    qu.offer(list[temp].get(i).next);
                }
            }
        }
        return false;
    }

문제 핵심

• Node를 활용하는 방법
• bfs or dfs
• 이진탐색