[백준/JAVA] 1414번: 불우이웃돕기

🔺 문제

1414번: 불우이웃돕기

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, sum;
    static int[] parent;            // 부모 노드
    static PriorityQueue<Edge> pq;  // 에지 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        parent = new int[N];
        for(int i = 0 ; i < N ; i++) parent[i] = i;
        
        // 에지 리스트에 저장
        pq = new PriorityQueue<>();
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            char[] chArr = st.nextToken().toCharArray();
            
            for(int j = 0 ; j < N ; j++) {
                int tmp = 0;
                
                if('a' <= chArr[j] && chArr[j] <= 'z')      tmp = chArr[j] - 'a' + 1;
                else if('A' <= chArr[j] && chArr[j] <= 'Z') tmp = chArr[j] - 'A' + 27;
                    
                sum += tmp; // 총 랜선 길이 저장
 
                if(i != j && tmp != 0)
                    pq.add(new Edge(i, j, tmp));
            }
        }
        
        // MST 수행 (= 최소 필요한 랜선 길이)
        int useEdge = 0;
        int result = 0; 
            
        while(!pq.isEmpty()) {
            Edge now = pq.poll();
            
            if(find(now.s) != find(now.e)) {
                union(now.s, now.e);
                result += now.v;
                useEdge++;
            }
        }
        
        if(useEdge == N - 1) System.out.println(sum - result);
        else                 System.out.println(-1);
 
    }
    
    // 유니온 파인드
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    public static int find(int a) {
        if(a == parent[a])   return a;
        else                 return parent[a] = find(parent[a]);
    }
}
 
class Edge implements Comparable<Edge> {
    int s, e, v;
    
    Edge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    
    @Override
    public int compareTo(Edge o) {
        return this.v - o.v;
    }
}

✅ 해결 아이디어
✔ 최소 신장 트리 - 크루스칼
→ 기부할 수 있는 랜선 길이의 최댓값 = 랜선 길이 총합 - 최소한으로 필요한 랜선 길이 (= MST수행 값)

 

💥 유의사항

•  입력 받은 값을 굳이 2차원 배열에 넣을 필요 없이, 변수를 사용해 바로 에지 리스트에 값 저장 가능 (변수 tmp)

•  소문자 : 현재 - ' a' + 1;   /  대문자 : 현재 - 'A' + 27

• 기부할 수 있는 랜선 길이의 최댓값  = 랜선 길이 총합 - 최소한으로 필요한 랜선 길이 (= MST 수행 값)

 

 

---

🔺 다른 풀이들

- 프림, 크루스칼 방법 모두 사용하심. & 결과 설명 굿

[JAVA] BOJ 1414 불우이웃돕기

 

 

- 다익스트라 활용하심

[Java] 백준 1414번 : 불우이웃돕기

 

 

- 에지 리스트 안 쓰시고 인접 리스트 쓰셨고 다른 부분도 참고용

: 소문자 대문자 구분도 Character.isLowerCase() 이런 거 사용하심

[백준, Java] 1414번 : 불우이웃돕기

 

---

💬 느낀 점

아이디어를 생각하지 못 하면 진짜 못 풀 것 같다...

근데 복습하면 괜찮을 것 같다!

 

이 MST 흐름에 대한 감이 좀 잡혔다.

 

 

1회독	2회독	3회독	4회독	5회독
V	6/27

 

 

(+ 6/27 2회독)

다 까묵...

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, sum;
    static PriorityQueue<Edge> pq;
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        // 변수들 초기화하기
        parent = new int[N];
        for(int i = 0 ; i < N ; i++)
            parent[i] = i;
        
        pq = new PriorityQueue<>();
 
        // 에지 리스트에 저장
        for(int i = 0 ; i < N ; i++) {
            char[] chArr = br.readLine().toCharArray();
            
            for(int j = 0 ; j < chArr.length ; j++) {
                int tmp = 0;
                
                if('a' <= chArr[j] && chArr[j] <= 'z') {
                    tmp = chArr[j] - 'a' + 1;
                }
                else if('A' <= chArr[j] && chArr[j] <= 'Z') {
                    tmp = chArr[j] - 'A' + 27;
                }
                sum += tmp; // 총 랜선 길이 저장
                
                if(i != j && tmp != 0) {
                    pq.add(new Edge(i, j, tmp));
                }
            }
        }
        
        // MST 수행
        int useEdge = 0;
        int result = 0;
        
        while(!pq.isEmpty()) {
            Edge now = pq.poll();
            
            if(find(now.s) != find(now.e)) {
                union(now.s, now.e);
                result += now.v;
                useEdge++;
            }
        }
        
        System.out.println((useEdge == N - 1) ? (sum - result) : -1);
    }
    
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b)  parent[b] = a;
    }
    private static int find(int a) {
        if(a == parent[a])  return a;
        return parent[a] = find(parent[a]);
    }
}
 
class Edge implements Comparable<Edge> {
    int s, e, v;
    
    public Edge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    
    @Override
    public int compareTo(Edge edge) {
        return this.v - edge.v;
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편