📙[Algo] 24.04.20 알고리즘

알고리즘 문제) BOJ 1414. 불우이웃돕기

1414번: 불우이웃돕기

문제 요약

• N개의 방에 각각 컴퓨터 한 개씩 존재
• 컴퓨터는 랜선으로 연결되어 있음
• 이때, N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.
• 그리고 나머지 랜선은 기부를 하려고 할 때, 기부할 수 있는 랜선의 길이의 최댓값 출력

시간 제한

• 2초

입력

• 컴퓨터 개수 N
  • 50보다 작거나 같은 자연수
• 랜선의 길이가 주어짐
  • i번째 줄의 j번째 문자가 0인 경우 컴퓨터 i와 j를 연결하는 랜선이 없음을 의미
  • 알파벳은 랜선의 길이
    • a~z : 1~26
    • A~Z : 27~52

출력

• 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력
  • 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1

접근법

• 관찰하기
  • 기부할 수 있는 랜선의 길이가 최댓값이 되려면, 선택한 랜선의 길이는 최소가 되어야 한다.
  • 즉, 길이(비용)이 최소가 되는 간선을 선택하기 위해 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구성하는 문제라고 생각했다.
• 사용 알고리즘 : 분리집합 & 크루스칼 알고리즘
• 주의할 점
  • 연결요소는 딱 하나로 모든 컴퓨터가 연결되어야 한다.
    • 최소 신장 트리 선택 후, find 메소드를 통해 같은 연결요소인지 한번더 체크했다.
  • 랜선이 1개일경우에는 total이 곧 answer값이 된다.

코드

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

public class Main {
    static int N;
    static ArrayList<int[]> graph;
    static int[] parent;

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

        parent[x] = find(parent[x]);
        return parent[x];
    }

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

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();

        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }

        String input;
        int total = 0;
        char alpha;
        for (int i = 1; i <= N; i++) {
            input = br.readLine();
            for (int j = 1; j <= N; j++) {
                alpha = input.charAt(j - 1);
                if (alpha == '0') continue;
                if (alpha - 'a' < 0) {
                    // 대문자
                    graph.add(new int[]{i, j, alpha - 'a' + 59});
                    total += alpha - 'a' + 59;
                } else {
                    // 소문자
                    graph.add(new int[]{i, j, alpha - 'a' + 1});
                    total += alpha - 'a' + 1;
                }
            }
        }

        Collections.sort(graph, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int answer = 0;
        int v1, v2, len;
        for (int i = 0; i < graph.size(); i++) {
            v1 = graph.get(i)[0];
            v2 = graph.get(i)[1];
            len = graph.get(i)[2];

            if (N > 1 && v1 == v2) continue;

            if (N > 1 && find(v1) == find(v2)) continue;

            answer += len;
            union(v1, v2);
        }

        boolean check = true;
        int p = find(1);
        for (int i = 2; i <= N; i++) {
            if (p != find(i)) {
                check = false;
            }
        }

        if (!check) bw.write("-1");
        else if (N == 1) bw.write(String.valueOf(answer));
        else bw.write(String.valueOf(total - answer));
        bw.flush();
        bw.close();
        br.close();
    }
}