jbw9964   1년 전

안녕하세요. 문제 풀이하다 잘 이해되지 않는 부분이 있어 질문 올립니다.

기본 아이디어 : 

- 이준석 학생을 정점으로 갖는 MST 구성했을 때, 간선들의 총합이 모든 학생을 친구로 만드는데 필요한 최소 비용일 것이다.

- 이준석 학생을 index=0 인 정점으로 생각하고, 입력으로 주어진 친구비용을 가중치로 갖는 N 개의 간선을 구성.

```

{(준석) ----> (학생 A), 비용 A},

{(준석) ----> (학생 B), 비용 B},

...

```

- MST 구성 후 간선 가중치 합이 K 를 넘거나 모든 정점이 이어지지 않았으면 `Oh no` 출력. 그렇지 않으면 가중치 합 출력.

위 아이디어를 바탕으로 아래와 같은 코드를 만들었습니다.

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import java.io.*;
import java.util.*;
import java.util.stream.*;
 
public class Main {
 
private static final BufferedReader br = new BufferedReader(
        new InputStreamReader(System.in)
    );
 
    private static int N, M;
    private static long K;
    private static PriorityQueue<Edge> edges;
    private static int[] parents;
 
    private static final int root = 0;
 
    private static void init() throws IOException {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Long.parseLong(st.nextToken());
 
        edges = new PriorityQueue<>(N);
        st = new StringTokenizer(br.readLine());
        for (int to = 1; to <= N; to++) {
            long cost = Long.parseLong(st.nextToken());
            edges.add(new Edge(to, cost));
        }
 
        parents = IntStream.rangeClosed(0, N).toArray();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
 
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
 
            int p1 = findParent(v1);
            int p2 = findParent(v2);
 
            if (p1 == p2) {
                continue;
            }
 
            int root = Math.min(p1, p2);
            int child = Math.max(p1, p2);
 
            parents[child] = root;
        }
 
    }
 
    private static int findParent(int v) {
        return parents[v] == v ? v : (parents[v] = findParent(parents[v]));
    }
 
    public static void main(String[] args) throws IOException {
 
        init();
 
        long minimumCost = getMstCost(root);
        
        int rootParent = findParent(root);
 
        boolean isEveryoneFriend = IntStream.rangeClosed(1, N)
                .map(Main::findParent)
                .allMatch(p -> p == rootParent);
 
        if (minimumCost > K || !isEveryoneFriend) {
            System.out.println("On no");
        } else {
            System.out.println(minimumCost);
        }
    }
 
    private static long getMstCost(int start) {
 
        long costSum = 0;
        edges.add(new Edge(start, 0));
 
        while (!edges.isEmpty()) {
            Edge e = edges.poll();
            int to = e.to;
 
            int startParent = findParent(start);
            int toParent = findParent(to);
 
            if (startParent == toParent) {
                continue;
            }
 
            costSum += e.cost;
 
            int root = Math.min(startParent, toParent);
            int child = Math.max(startParent, toParent);
 
            parents[child] = root;
        }
 
        return costSum;
    }
}
 
class Edge implements Comparable<Edge> {
 
    final int to;
    final long cost;
 
    public Edge(int to, long cost) {
        this.to = to;
        this.cost = cost;
    }
 
    @Override
    public int compareTo(Edge o) {
        return Long.compare(this.cost, o.cost);
    }
 
    @Override
    public String toString() {
        return "Edge{" +
               "to=" + to +
               ", cost=" + cost +
               '}';
    }
}
 
cs

하지만 채점하니 틀렸었고 여러 방식을 시도하다 아래 코드는 성공하는 것을 발견했습니다.

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
public static void main(String[] args) throws IOException {
 
    init();
 
    long minimumCost = getMstCost(root);
 
    if (minimumCost > K) {
        System.out.println("Oh no");
    } else {
        System.out.println(minimumCost);
    }
 
 
//    int rootParent = findParent(root);
//
//    boolean isEveryoneFriend = IntStream.rangeClosed(1, N)
//            .map(Main::findParent)
//            .allMatch(p -> p == rootParent);
//
//    if (minimumCost > K || !isEveryoneFriend) {
//        System.out.println("On no");
//    } else {
//        System.out.println(minimumCost);
//    }
}
cs

이 둘의 차이가 뭘까요..?

tjdnfls1234   1년 전

같은 그룹에 속해있더라도 경로 압축 전엔 부모가 다른 경우가 있습니다.

예를 들어 (2 3) , (1 3)을 순서대로 연결한다고 할 때

(2 3) -> parents[3] = 2 , parents[2] = 2

(1 3) -> parents[2] = 1 , parents[1] = 1

이므로, 여전히 3번 정점의 부모는 2번입니다.

어짜피 MST는 모든 정점이 연결될 수 있는 최소 비용이기 때문에 비용만 비교해도 무방합니다.

jbw9964   1년 전

> @tjdnfls1234

하지만findParent메서드를 통해 각 부모를 확인하므로

정답 판별 시점엔 모든 경로가 압축되지 않나요?

MST 구성후 parents[] = [0, 0, 1, 2, 3] 과 같이 존재해도

findParent(2) ==> (parents[2] = findParent(1)) ----> (parents[1] = findParent(0)) ----> return 0

처럼 재귀해 정답 판별시점엔 무관하지 않을까 궁금합니다...!

bumsoo0515   1년 전

기존 코드에 오타가 있네요. Oh no가 아니라 On no라고 적혀 있습니다.

jbw9964   1년 전

????? 아니 이런 실수를.....

고맙습니다....... ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.