백준 1939번 - 중량제한 (java)

💡 문제 링크

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

 

- 첫 풀이(실패)

처음에 시도한 풀이는 아래와 같다.

 

출발지에서 도착지까지의 모든 경로를 구하면서 해당 경로 상에서 가장 작은 중량을 구하고,

모든 경로의 값들과 비교해 그 중에서 가장 큰 중량을 구하려고 했다.

그 과정에서 이미 구한 가장 작은 중량보다 더 작은 값은 가지치기하려고 했다.

 

조금 틀린 코드이기도 하지만 그 전에 우선 시간 초과가 났다.

"서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며" 라는 조건 때문에

섬에 방문 처리를 할 수가 없어(백트래킹으로 dfs 후 visited를 다시 false 처리함)

시간 초과가 난 것 같다.

틀린 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int N, M;
    public static List<int[]>[] adjacent;
    public static int island1, island2;
    public static int maxMin;
    public 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());

        adjacent = new List[N+1];
        visited = new boolean[N+1];

        for (int i = 0; i <= N; i++) {
            adjacent[i] = new ArrayList<int[]>();
        }

        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());
            adjacent[a].add(new int[]{b, c});
            adjacent[b].add(new int[]{a, c});
        }
        st = new StringTokenizer(br.readLine());
        island1 = Integer.parseInt(st.nextToken());
        island2 = Integer.parseInt(st.nextToken());

        visited[island1]=true;
        dfs(island1, Integer.MAX_VALUE);

        System.out.println(maxMin);

    }

    public static void dfs(int a, int min) {
        if(a==island2){
            maxMin=Math.max(min,maxMin);
            return;
        }
        for (int[] cur : adjacent[a]) {
            int b = cur[0];
            int c = cur[1];
            if (!visited[b]) {
                if (c < maxMin) {
                    return;
                }
                visited[b] = true;
                dfs(b, Math.min(min, c));
                visited[b] = false;
            }
        }
    }
}

---

 

결국 다른 블로그를 참고하여 문제를 풀었다.

총 2가지 방법으로 문제를 풀었다.

1. 이분탐색 + bfs/dfs

2. union find 활용

개인적으로 2번 방법이 훨씬 직관적이고 좋았다..

 

💡 Sol 1. 이분탐색 + bfs/dfs

- 아이디어

1) 이진탐색을 통해 해당 중량(mid)이 A에서 B로 이동이 가능한지 DFS탐색을 통해 조사한다.

• 이동이 가능하면 ->  중량을 늘려서 다시 탐색한다.  low = mid +1;  + answer에 현재 mid 값을 저장한다.
• 이동이 불가능하면 -> 중량을 줄여준 다음 다시 탐색한다. high = mid-1;

2) answer을 출력한다.

 

- 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G3_1939_중량제한_sol1 {
    public static int N, M;
    public static List<int[]>[] adjacent;
    public static int island1, island2;
    public static int answer;
    public static boolean visited[];
    public static int 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());

        adjacent = new List[N + 1];

        for (int i = 1; i <= N; i++) {
            adjacent[i] = new ArrayList<int[]>();
        }

        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());
            weight = Math.max(weight, c);
            adjacent[a].add(new int[]{b, c});
            adjacent[b].add(new int[]{a, c});
        }

        st = new StringTokenizer(br.readLine());
        island1 = Integer.parseInt(st.nextToken());
        island2 = Integer.parseInt(st.nextToken());

        int low = 1;
        int high = weight; //입력 받은 중량 중 최댓값으로 초기화

        while (low <= high) {
            visited = new boolean[N + 1];
            int mid = (low + high) / 2;
            if (bfs(mid)) { //해당 중량을 견딜 수 있는 경우
                low = mid + 1;
                answer = mid;
            } else { //해당 중량을 견딜 수 없는 경우
                high = mid - 1;
            }
        }

        System.out.println(answer);

    }

    public static boolean bfs(int mid) {
        Queue q = new ArrayDeque<Integer>();
        visited[island1] = true;
        q.offer(island1);

        while (!q.isEmpty()) {
            int cur = (int) q.poll();
            if (cur == island2) {
                return true;
            }
            for (int[] next : adjacent[cur]) {
                if (!visited[next[0]]) {
                    if (next[1] >= mid) {
                        q.offer(next[0]);
                        visited[next[0]] = true;
                    }
                }
            }
        }
        return false;
    }
}

 

✔️ 여기서는 방문처리를 하네?

처음 실패한 코드에서는 "서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며" 라는 조건 때문에 방문 처리를 하지 못했다.

그런데 여기서는 하네?

해당 풀이는 A지점에서 B지점까지의 모든 경로를 구한 후 그 값을 비교하는 것이 아니라,

하나라도 A지점에서 B지점까지 가는 경로가 있으면 되는 풀이이기 때문에(해당 중량이 갈 수 있는지만 체크)

다리를 건널 수 있는 경우를 만나면 visited 처리를 해도 아무 문제가 없다.

 

✔️ 왜 (1)1~최대 중량값을 전체를 이분탐색할까? (2)입력 받은 중량값들 안에서만 이분탐색하지 않고?

(1)방법은 총 10억개의 값, (2)방법은 최대 100,000개의 값을 이분탐색하면 된다.

그럼에도 (1) 방법을 하는 이유는, (2) 방법은 입력 받은 중량값들을 정렬해야 하기 때문이다.

(2번 방법으로 해도 전혀 문제 없다! 다만, 풀이를 보며 왜 이렇게 했을까 의문이 들어 정리를 하는 바이다.)

bfs는 둘 다 동일하니 제외하고 생각해보자.

(1) 시간복잡도

이분탐색의 시간복잡도는 O(logN)이므로 O(log10억) = 9

(2) 시간복잡도

Arrays.sort()의 시간복잡도는 평균 O(NlogN). 여기서 N에 M의 값이 들어가므로, O(MlogM).

이분탐색의 시간복잡도는 O(logM)

결국 전체 O(MlogM)으로 생각하면 된다.

M은 최대 100,000이므로 O(MlogM) = 500,000

 

결론) 이분탐색에 비해 Arrays.sort의 시간복잡도가 매우 커서 (1) 방법이 더 빠르다. 그러나 (2) 방법도 아주 무난하게 통과한다.

 

💡 Sol 2. union find 활용

- 아이디어

1) 다리를 리스트에 넣고, 중량을 기준으로 내림차순 정렬한다.

2) 순서대로 다리가 잇고 있는 2개의 섬을 union한다.

3) 출발지와 목적지가 하나의 union에 들어가 있는지 확인한다.

• 들어가 있으면, 해당 순서의 다리 중량이 최댓값이므로 종료한다.
• 들어가 있지 않으면, 2)번으로 돌아가 반복한다.

- 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G3_1939_중량제한_sol2 {
    public static int N, M;
    public static List<Edge> edges;
    public static int island1, island2;
    public static int[] rank, parent;

    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());

        edges = new ArrayList<Edge>();
        rank = new int[N + 1];
        parent = new int[N + 1];

        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());
        island1 = Integer.parseInt(st.nextToken());
        island2 = Integer.parseInt(st.nextToken());


        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o2.w < o1.w) {
                    return -1;
                }
                if (o2.w > o1.w) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });

        int answer = 0;
        makeSet();

        for (Edge cur : edges) {
            union(cur.s, cur.e);
            if (find(island1) == find(island2)) {
                answer = cur.w;
                break;
            }
        }
        System.out.println(answer);
    }

    public static void makeSet() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }

    public static boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) {
            return false;
        }

        if (rank[a] < rank[b]) {
            rank[b] += rank[a];
            parent[a] = b;
        } else {
            rank[a] += rank[b];
            parent[b] = a;
        }
        return true;
    }

    public static class Edge {
        int s; //노드1
        int e; //노드2
        int w; //가중치

        Edge(int s, int e, int w) {
            this.s = s;
            this.e = e;
            this.w = w;
        }
    }

}

 

 

알고 보면 풀이가 딱히 안 어려워 보이는데,, 모를 땐 좀 힘들었던 문제였다. (그것이 바로 너의 실력이란다..흑)

심지어 나름 길고 오래 걸렸던 이 포스팅을 한 번 날려 먹고 다시 쓰느라 힘들었다..

아무튼 고생해따