[백준] 16562번 친구비 문제 풀이

문제

이미지를 클릭하면 문제 페이지로 이동합니다.

 

 

풀이

고려해야할 점

• 친구의 친구의 친구도 친구로 칠 수 있다. 즉 어떤 친구 집단 트리 A가 있을 때 그 중 한 명만 친해도 그 집단 전체와 친구가 되었다고 할 수 있다. 
• 이를 계산하기 위해 서로 연결되어 있는 친구 집단을 구해야 한다. 이 결과를 바탕으로 친구비를 최소로 하는 경우의 수를 찾아야 한다. 
• 중복되는 친구 관계, 혹은 자기 자신과 친구인 경우를 확인해야 한다. 
• 모두 친구를 만들 수 없는 경우 "oh no"를 출력해야 한다. 

 

알고리즘 분류(백준 기준)

• 자료구조
• 그래프 이론 
• 그래프 탐색
• 분리 집합
• 유니온 파인드 

 

풀이 아이디어

• 집합 관계를 효율적으로 판별하기 위해 유니온 파인드를 사용하였다. 두 집합을 합칠 때는 친구비의 값이 더 싼 쪽이 부모가 되도록 결합하였다. 
• 각 집합의 최상위 부모가 가장 친구비가 낮으므로 각 집합의 최상위 부모를 찾아 그 값을 더해 친구비 최솟값을 구하였다. 
• 혹시나 Union Find 코드에 대해 알고 싶다면 아래 링크 참조 

[알고리즘]크루스칼 알고리즘(kruskal's Algorithm) 정리 및 백준 문제 추천

최적화 아이디어

• 유니온 파인드 결합을 진행할 때 부모의 위치를 최상위 부모의 값으로 갱신하도록 하였다. 부모 탐색 시간 감소 
• 최상의 부모를 찾을 때, 자신의 부모가 자신인 것들을 기준으로 찾았다. O(n)으로 탐색 가능. 코드 구현이 간단하다. 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] cost, parent, minCost;

    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()); // 친구 관계 수 (간선 개수)
        int k = Integer.parseInt(st.nextToken()); // 사용할 수 있는 최대 비용
        
        cost = new int[n+1];   // 각 학생의 비용을 저장하는 배열
        parent = new int[n+1]; // 각 노드의 부모 노드를 저장하는 배열 (Union-Find용)
        minCost = new int[n+1]; // 각 그룹의 최소 비용을 저장하는 배열
        int result = 0;         // 친구 관계 최소 비용의 합산 결과

        // 각 학생의 친구 비용을 입력받음
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
            parent[i] = i;      // 초기에는 각 노드가 자기 자신을 부모로 가짐
            minCost[i] = cost[i]; // 초기화 시 각 노드의 비용이 그룹의 최소 비용
        }

        // 친구 관계를 입력받아 Union-Find 구조로 그룹을 만듦
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken()); // 친구 관계의 첫 번째 학생
            int w = Integer.parseInt(st.nextToken()); // 친구 관계의 두 번째 학생
            union(v, w); // 두 학생을 같은 그룹으로 묶음
        }

        // 그룹의 최소 비용을 모두 합산
        for(int i = 1; i <= n; i++) 
            if(parent[i] == i) result += minCost[i]; // 루트 노드인 경우 그룹의 최소 비용을 더함

        // 총 비용이 사용할 수 있는 최대 비용을 초과하면 "Oh no" 출력
        if(result > k) System.out.print("Oh no");
        else System.out.print(result); // 아니면 총 비용 출력
    }

    // Union 연산: 두 노드를 같은 그룹으로 합침
    static void union(int x, int y) {
        int nX = find(x); // x의 루트 노드 찾기
        int nY = find(y); // y의 루트 노드 찾기

        if(nX != nY) { // 두 노드의 루트가 다르면 그룹을 합침
            // 비용이 더 작은 쪽이 새로운 루트가 되도록 설정
            if(minCost[nX] < minCost[nY]) {
                parent[nY] = nX;
                minCost[nX] = Math.min(minCost[nX], minCost[nY]);
            } else {
                parent[nX] = nY;
                minCost[nY] = Math.min(minCost[nX], minCost[nY]);
            }
        }
    }

    // Find 연산: 현재 노드의 루트 노드를 찾음 (경로 압축 포함)
    static int find(int now) {
        if(parent[now] != now) 
            parent[now] = find(parent[now]); // 재귀적으로 부모를 찾으며 경로 압축
        return parent[now];
    }
}