백준 1939번: 중량제한 (Java)

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

1939번: 중량제한

 

 

 

 

 

 

 

---

 

나의 접근 방법

N = 10000, M = 100000이므로 O(N^2)보다 작은 시간복잡도를 갖는 풀이가 있을 거라 생각했습니다. 시작점을 기준으로 특정 점까지 가는 거리를 구하는 문제이기에, 다익스트라에서 로직을 살짝 바꿔주면 될 거라고 생각했습니다. 한 번 틀렸는데, min을 써야할 곳에 max를 쓰는 실수를 고치니 정답을 얻었습니다.

 

풀이

풀이 1. BFS + 매개변수 탐색

물체의 무게에 대해 매개변수 탐색을 하여, 운반할 수 있는 가장 큰 무게를 찾으면 됩니다.

시간 복잡도는 O(M*log(10억)) 입니다.

 

풀이 2. 유니온 파인드 변형

다리를 중량제한의 내림차순으로 정렬한 후, 각 다리를 꺼내면서 다리의 양 지점을 연결해줍니다. 현재 연결 상태를 union-find를 통해, '섬 a, b가 연결되어있다 <=> a와 b의 부모가 동일하다'로 저장합니다.

계속 연결하다가, 시작점과 끝점이 연결되어있는 경우(=시작점과 끝점의 부모가 동일한 경우) 연결 작업을 끝냅니다. 정답은 현재까지 나온 다리의 중량제한 중 가장 작은 값이 됩니다. 시간 복잡도는 O(M*logM)입니다.

 

풀이 3. 다익스트라 변형

시작점 s에서 점 x까지 갈 수있는 최대 중량을 1차원 정수 배열 dist에 기록합니다. 초기값을 '연결이 되어있지 않음'의 의미로 -INF, 시작점의 값 dist[s]를 INF로 기록해둡니다.

다익스트라랑 비슷하게 코드를 적되, min(dist[현재 위치], (현재 다리의 최대 중량)이 dist[다음 위치]보다 크면 최댓값이 갱신되는 경우이므로 방문해줍니다. 위와 마찬가지로 시간 복잡도는 O(M*logM)입니다.

 

다양한 풀이가 있어서 공부하는 재미가 있는 문제였습니다. 개인적으로는 '풀이 1'이 가장 범용적이고, 알아두면 좋은 풀이가 아닌가 싶습니다.

 

코드

풀이 1: BFS + 매개변수 탐색

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        final int INF = 1_000_000_007;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        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());
            graph.get(A).add(new Edge(B, C));
            graph.get(B).add(new Edge(A, C));
        }
        
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int l = 1, r = 1_000_000_000;
        while (l <= r) {
            int mid = (l + r) / 2;
            boolean[] visited = new boolean[N+1];
            visited[s] = true;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(s);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (Edge edge: graph.get(cur)) {
                    if (visited[edge.loc] || edge.dist < mid) continue;
                    queue.offer(edge.loc);
                    visited[edge.loc] = true;
                }
            }
            if (visited[e]) l = mid + 1;
            else r = mid - 1;
        }
        System.out.println(r);
    }
    
    static class Edge {
        int loc;
        long dist;
 
        public Edge(int loc, long dist) {
            this.loc = loc;
            this.dist = dist;
        }
    }
}
 

 

풀이 2: 유니온 파인드 활용 (크루스칼 알고리즘)

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] p;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        List<Edge> edges = 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());
            edges.add(new Edge(A, B, C));
        }
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        
        Collections.sort(edges);
        makeSet(N);
        long ans = 1_000_000_000;
        for (int i = 0; i < edges.size(); i++) {
            Edge edge = edges.get(i);
            if (!union(edge.from, edge.to)) continue;
            ans = Math.min(ans, edge.dist);
            if (findRoot(s) == findRoot(e)) break; 
        }
        System.out.println(ans);
    }
    
    static class Edge implements Comparable<Edge> {
        int from, to;
        long dist;    
 
        public Edge(int from, int to, long dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
        
        public int compareTo(Edge o) {
            return -Long.compare(this.dist, o.dist);
        }
    }
    
    static void makeSet(int N) {
        p = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            p[i] = i;
        }
    }
 
    static int findRoot(int a) {
        if (a == p[a]) return a;
        return p[a] = findRoot(p[a]);
    }
 
    static boolean union(int a, int b) {
        a = findRoot(a);
        b = findRoot(b);
        if (a == b) return false;
        p[b] = a;
        return true;
    }
}
 

 

풀이 3: 다익스트라 응용

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        final int INF = 1_000_000_007;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        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());
            graph.get(A).add(new Edge(B, C));
            graph.get(B).add(new Edge(A, C));
        }
        
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        long[] dist = new long[N+1];
        Arrays.fill(dist, -INF);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        dist[s] = INF;
        pq.offer(new Edge(s, INF));
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (dist[cur.loc] > cur.dist) continue;
            for (Edge nxt: graph.get(cur.loc)) {
                if (Math.min(dist[cur.loc], nxt.dist) > dist[nxt.loc]) {
                    dist[nxt.loc] = Math.min(dist[cur.loc], nxt.dist);
                    pq.offer(new Edge(nxt.loc, dist[nxt.loc]));
                }
            }
        }
        System.out.println(dist[e]);
    }
    
    static class Edge implements Comparable<Edge> {
        int loc;
        long dist;
 
        public Edge(int loc, long dist) {
            this.loc = loc;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return -Long.compare(this.dist, o.dist);
        }
 
        public String toString() {
            return "Edge [loc=" + loc + ", dist=" + dist + "]";
        }
    }
}
 

 

 

시간 비교

위에서부터 풀이 1, 2, 3을 비교했습니다. 성능상으로 보면 1 < 2 < 3으로 보이나, 미미한 차이라 큰 의미는 없는 듯합니다.