[BOJ1414] 불우이웃돕기 (프림, 최소 신장트리, 그리디)

 

 

---

문제 링크

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

1414번: 불우이웃돕기

 

문제 풀이

- 프림 알고리즘(최소 신장트리) 사용하여 풀이

- 시간 복잡도  : O(ElogV)

 

절차

1) 모든 컴퓨터(노드)를 연결하는 최소 랜선 길이(비용)을 구한다.

2) 다솜이가 가진 총 랜선 길이에서 최소 랜선 길이 뺀 나머지를 기부 한다

 

알파벳이 소문자인지, 대문자인지 구분하는 방법이 조금 애매했는데
이번 문제를 통해 Character 클래스에 유용한 메서드를 알게 되었다.

// 알파벳 -> 숫자 ( a ~ z : 1 ~26, A ~ z : 27 ~ 52)
private static int convertAlphabet(char alphabet) {
    if(Character.isLowerCase(alphabet)) return alphabet - 'a' + 1;
    else if(Character.isUpperCase(alphabet)) return alphabet - 'A' + 27;
    return 0;
}

 

 

제출 코드 

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static int N;

    static List<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int idx;
        int cost;

        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge other) {
            return cost - other.cost; // 내림차순
        }

    }

    private static int convertAlphabet(char alphabet) {
        if(Character.isLowerCase(alphabet)) return alphabet - 'a' + 1;
        else if(Character.isUpperCase(alphabet)) return alphabet - 'A' + 27;
        return 0;
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        adj = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        int totalLen = 0;
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            char[] line = st.nextToken().toCharArray();
            for(int j = 1; j <= N; j++) {
                if(line[j - 1] == '0') continue;

                int cost = convertAlphabet(line[j - 1]);
                adj[i].add(new Edge(j, cost));
                adj[j].add(new Edge(i, cost));

                totalLen += cost;
            }
        }

        // 시작 노드를 i 로 노드를 모두 연결하는 최소 비용 찾는다
        int result = Integer.MAX_VALUE;
        for(int i = 1; i <= N; i++) {
            result = Math.min(result, pro(i));
        }

        // 최소 비용을 제외한 나머지 랜선을 기부한다
        if(result == -1) sb.append("-1");
        else sb.append(totalLen - result);

        System.out.println(sb);
    }

    static int pro(int start) {
        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(start, 0));

        boolean[] visit = new boolean[N + 1];

        int result = 0;
        int edgeCnt = 0;
        while(!que.isEmpty()) {
            Edge cur = que.poll();

            if(visit[cur.idx]) continue;

            visit[cur.idx] = true;
            result += cur.cost;
            edgeCnt += 1;

            for(Edge next : adj[cur.idx]) {
                if(visit[next.idx]) continue;

                que.add(next);
            }
        }

        return edgeCnt == N ? result : -1;
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}