💡문제
19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!
학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.
준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!
위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.
입력
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.
두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)
다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.
출력
준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.
예제입력
5 3 20
10 10 20 20 30
1 3
2 4
5 4예제출력
20📖내가 작성한 Code
import sys
'''
n이 1만
모든 학생과 친구
학생 i 에게 ai 만큼 돈 주면 1달간 친구. 가장 적은 비용으로 모든 사람과 친구
'''
class UnionFind:
def __init__(self, data):
self.people = data + 1
self.parent = [i for i in range(self.people)]
def find(self, children):
if self.parent[children] != children:
return self.find(self.parent[children])
return children
def union(self,left_node, right_node):
left_node_parent = self.find(left_node)
right_node_parent = self.find(right_node)
if left_node_parent < right_node_parent:
self.parent[right_node_parent] = left_node_parent
else:
self.parent[left_node_parent] = right_node_parent
def find_first_parent(self):
return [self.find(i) for i in range(self.people)]
def find_min_friends_cost(processed_friends, friends_cost, k):
min_friends_cost_dict = {}
for friend,cost in zip(processed_friends,friends_cost):
current_min = min_friends_cost_dict.get(friend, cost)
min_friends_cost_dict.update({friend: min(current_min, cost)})
if (min_friends_cost := sum(min_friends_cost_dict.values())) > k:
return 'Oh no'
return str(min_friends_cost)
def main():
inputs = map(int, sys.stdin.read().split())
n, m, k = next(inputs), next(inputs), next(inputs)
friends_cost = [next(inputs) for _ in range(n)]
new_parent = UnionFind(n)
for _ in range(m):
new_parent.union(next(inputs), next(inputs))
sys.stdout.write(find_min_friends_cost(new_parent.find_first_parent()[1:], friends_cost, k))
if __name__ == '__main__':
main()
✍️풀이과정
유니온 파인드를 각각의 함수화 하려니까 parents를 전역에 설정해야하는데 그게 싫어서 class로 만들어버렸다. 전형적인 유니온 파인드 문제. 최적화는 안했음.
🧠 코드 리뷰
-
find 메서드 : 재귀적으로 부모를 찾는 방식은 직관적이지만, 경로 압축(path compression)이 적용되어 있지 않습니다. 경로 압축을 도입하면 한 번의 find 이후 부모 연결을 직접 갱신하여 후속 호출의 시간 효율을 높일 수 있습니다.
-
딕셔너리 업데이트 방식: 현재 코드에서는 매번min_friends_cost_dict.update({friend: min(current_min, cost)})를 사용하는데, 이는 불필요한 딕셔너리 생성 오버헤드가 있습니다.
대신 단순 대입(min_friends_cost_dict[friend] = min(...))을 사용하면 효율성이 개선됩니다.
🛠️Java 연습 코드
import java.io. *;
import java.util.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = br.readLine();
if (line == null) return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static class UnionFind {
int[] parent;
public UnionFind(int n){
parent = new int[n+1];
for (int i = 0; i <= n; i++){
parent[i] = i;
}
}
public int find(int a){
if (parent[a] != a) {
parent[a] = find(parent[a]);
}
return parent[a];
}
public void union(int a, int b){
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return;
}
if (rootA < rootB) {
parent[rootB] = rootA;
} else {
parent[rootA] = rootB;
}
}
}
public static void main(String[] args) throws IOException {
FastReader fr = new FastReader();
int n = fr.nextInt();
int m = fr.nextInt();
int k = fr.nextInt();
int[] friendCost = new int[n + 1];
for (int i = 1; i <= n; i++) {
friendCost[i] = fr.nextInt();
}
UnionFind uf = new UnionFind(n);
for (int i = 0; i < m; i++) {
int a = fr.nextInt();
int b = fr.nextInt();
uf.union(a, b);
}
int INF = 1_000_000_000;
int[] minCost = new int[n + 1];
Arrays.fill(minCost, INF);
for (int i = 1; i <= n; i++) {
int root = uf.find(i);
minCost[root] = Math.min(minCost[root], friendCost[i]);
}
long totalCost = 0;
for (int i = 1; i <= n; i++) {
if (uf.find(i) == i) {
totalCost += minCost[i];
}
}
System.out.println(totalCost <= k ? totalCost : "Oh no");
}
}
💻결과
🖱️참고 링크
