[백준 1414] 불우이웃돕기 (Java) - 최소신장트리, 유니온파인드

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

불우이웃돕기

문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 복사

3
abc
def
ghi

예제 출력 1 복사

40

 

---

풀이

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

public class Main {
    static int N;
    static int[][] A;
    static ArrayList<LAN> lans;
    static int count;
    static int[] parent;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 컴퓨터 개수
        A = new int[N][N]; // 랜선정보 저장
        int totalLength = 0;

        // 랜선정보 입력받아서 -> 정수형으로 저장하기
        for(int i=0; i<N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                if (Character.isLowerCase(chars[j])) {
                    // 현재 문자가 소문자라면
                    A[i][j] = chars[j] - 'a' + 1;
                    totalLength += A[i][j];
                } else if (Character.isUpperCase(chars[j])){
                    // 현재 문자가 대문자라면
                    A[i][j] = chars[j] - 'A' + 27;
                    totalLength += A[i][j];
                }else{
                    // '0'이라면
                    A[i][j] = chars[j] - '0';
                }
            }
        }

        // 랜선정보 담는 리스트 (중복저장 방지)
        lans = new ArrayList<>();
        for (int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if (i==j) continue;
                if (A[i][j] > 0) {
                    lans.add(new LAN(i, j, A[i][j])); // 시작노드, 도착노드, 랜선길이
                }
            }
        }

        // 랜선의 length 기준으로 오름차순 정렬
        Collections.sort(lans, Comparator.comparingInt(a -> a.length));

        count = 0; // 연결 랜선개수
        parent = new int[N]; // 대표노드 배열 초기화
        for (int i=0; i<N; i++){
            parent[i] = i; // 내 자신이 대표노드
        }

        int usedLength = 0; // 사용된 랜선길이
        for(LAN lan : lans){
            // 랜선 사용개수가 N-1개가 되면 종료
            if(count > N-1) break;

            if (find(lan.start) != find(lan.end)){
                union(lan.start, lan.end);
                usedLength += lan.length; // 합계에서 사용한 랜선길이 빼주기
                count++; // 랜선사용 개수 증가
            }
        }
        System.out.println(count == N-1 ? totalLength - usedLength : -1);
    }
    private static int find(int a){
        if (parent[a] == a) return a;
        return parent[a] = find(parent[a]); // 자신의 대표노드 찾아서 넣어줌
    }

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

        if (a != b){ // a와 b의 대표노드가 서로 다르다면 union 연산
            parent[b] = a;
        }
    }
}
class LAN implements Comparable<LAN> {
    int start;
    int end;
    int length;

    public LAN(int start, int end, int length){
        this.start = start;
        this.end = end;
        this.length = length;
    }
    @Override
    public int compareTo(LAN o) {
        return this.length - o.length; // 길이 기준 오름차순 정렬
    }
}

입력데이터

• 입력으로 주어진 데이터가 설명이 뭔가 불분명해서 이해하기 어려웠다
• 해석해보자면 컴퓨터 3대가 있을 때, 3X3 행렬로 컴퓨터연결 랜선 정보가 주어진다.
• 그런데 숫자가 아닌 문자(알파벳 혹은 0)으로 주어지기 때문에 이를 계산해서 정수형으로 바꿔주는 것부터 관건이다.
• a ~ z : 1 ~ 26을 나타내고 A ~ Z : 27 ~ 52를 나타낸다.
• 입력이 아래와 같이 주어진다고 가정하자. 아래 문자를 랜선길이로 변환하면 아래와 같다.

a	b	c
d	e	f
g	h	i

 

1	2	3
4	5	6
7	8	9

• 그리고 각각이 나타내는 의미는, 위 배열을 A라고 가정할 때 A[i][j]의 의미는 i컴퓨터와 j컴퓨터를 이어주는 랜선정보이다.

---

풀이과정

• 컴퓨터개수 N을 입력받아 NXN크기의 인접행렬을 선언한다.
• 랜선입력 정보를 받을 때 정수형으로 변환해서 저장한다.
  • 한줄 읽어들인 것을 -> charArray로 변환한뒤, 문자를 하나하나 읽어들이면서
  • 소문자라면 : A[i][j] = chars[j] - 'a' + 1으로 저장 후 , totalLength에 같이 더해준다.
  • 대문자라면 : A[i][j] = chars[j] - 'A' + 27으로 저장 후, totalLength에 같이 더해준다.
  • 0이라면 A[i][j] = chars[j] - '0'을 저장해준다.
• 랜선정보 리스트를 선언한 뒤, 랜선정보를 저장한다.
  • 이를 위해서 LAN이라는 사용자정의 클래스를 정의해주었다.
  • start, end, length로 이루어진다.
  • i==j 일때는 자기자신을 연결할 수 없으므로 무시하고 수행한다. 그리고 랜선길이 값이 0이 아닐 때만 저장해준다.
• 랜선정보 리스트 lans를 length기준으로 오름차 정렬을 수행해준다.
• MST를 수행하기 위해서는 사전에 유니온파인드가 수행되어야 한다.
• length가 가장 짧은 랜선을 가지고 연결을 시도하되, find연산을 통해 각각의 대표노드가 서로 다른지 확인한 뒤, 서로의 대표노드가 다를 때만 union 연산을 해준다. 
  • union 연산 시, 사용한 랜선의 length를 더해주고, count값을 증가시켜준다.
  • 이 count값이 N-1이 될때까지 반복한다.
• 모든 연산을 수행하고 나서 count값이 N-1이 아니라면 모든노드를 연결하는데 실패한 것이므로 -1을 출력한다.
• 만약 count값이 N-1이라면 기부할 수 있는 랜선의 길이(totalLength - usedLength)를 출력한다.