[JAVA]13418 학교 탐방하기, 골드 3

 📚 문제  

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

13418번: 학교 탐방하기

🔍 아이디어  

mst를 활용하여 풀이하였습니다.

*(다른 분들과 풀이가 달라 맞는 풀이인지 확신이 들지 않습니다. 참고 부탁드립니다)

 

가장 힘이 드는경우는 가장 많은 경사로(같은 길이 나오지 않기때문)를 이용하는 경우라고 생각하였습니다

따라서 먼저 경사로를 이용하는 경우의 모든 경로를 연결합니다. 이때 연결된 경사로의 개수의 제곱이 점수가 됩니다.

가장 힘이 적게 드는 경우는 경사로를 이용하지 않고 내리막길을 가장 많이 이용해야 합니다. 

이때는 만약 union하는 경우에 사용한 길의 개수에서 빼서 경사로로 가야만 하는 길의 개수를 구할 수 있습니다.

 

이렇게 구한 두개의 점수의 차를 구하여 제출하여 통과하였습니다.

📝 풀이 

package 백준.graph.mst.kruskal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Boj_13418_학교탐방하기 {
    private static class Road {
        int start;
        int end;

        public Road(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()) + 1; //city
        int m = Integer.parseInt(st.nextToken()) + 1;

        List<Road> slopes = new ArrayList<>(); //경사로들만
        List<Road> descs = new ArrayList<>(); //내리막길말


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int slope = Integer.parseInt(st.nextToken());
            if (slope == 0) {
                slopes.add(new Road(start, end));
            } else {
                descs.add(new Road(start, end));
            }
        }
        parents = new int[n];

        //경사로 연결할 수 있는 만큼 연결하는 경우
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }

        int maxCnt = 0;
        for (Road slope : slopes) {
            if (union(slope.start, slope.end)) {
                maxCnt++;
            }
        }

        //내려가는 길을 연결할 수 있는 만큼 연결하는 경우
        int minCnt= n-1;
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }

        for (Road desc : descs) {
            if(union(desc.start, desc.end)){
                minCnt--;
            }
        }

        System.out.println((maxCnt * maxCnt) - (minCnt * minCnt));
    }

    private static boolean union(int a, int b) {
        a = findParent(a);
        b = findParent(b);

        if (a != b) {
            if (a < b) parents[b] = a;
            else parents[a] = b;
            return true;
        }
        return false;
    }

    private static int findParent(int a) {
        if (a == parents[a]) return a;
        return parents[a] = findParent(parents[a]);
    }
}