[백준 13418/JAVA] 학교 탐방

문제

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

13418번: 학교 탐방하기

풀이

kruskal 알고리즘으로 MST 구현

최적의 경우 내리막을 우선순위로 골라 MST를 만들고 최악의 경우 오르막을 우선순위로 골라 MST를 만들면 된다.
내리막 = 1, 오르막 = 0으로 표현되었으므로 내림차순으로 정렬하고
최적의 경우 정렬된 리스트 순서대로 선택, 최악의 경우는 정렬된 리스트의 반대 순서로 선택.
오르막이 나올 때마다 sum++으로 피로도를 증가시킨다.

코드

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

public class Main {
    static int V;
    static int[] parent;
    static List<Edge> edgeList;

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

        //노드 수, 엣지 수
        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        edgeList = new ArrayList<>();
        int sum = 0;

        //부모 노드 초기화
        parent = new int[V+1];
        for(int i=0; i<V+1; i++)
            parent[i] = i;

        //노드, 기울기
        for(int i=0; i<=E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edgeList.add(new Edge(a, b, c));
        }

        Collections.sort(edgeList);

        //최적: 내리막(1) 먼저 선택
        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.x, edge.y)){
                union(edge.x, edge.y);
                if(edge.slope == 0)
                    sum++;
            }
        }

        int best = (int)Math.pow(sum,2);
        sum = 0;
        for(int i=0; i<V+1; i++)
            parent[i] = i;

        //최악: 오르막(0) 먼저 선택
        for(int i=edgeList.size()-1; i>=0; i--){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.x, edge.y)){
                union(edge.x, edge.y);
                if(edge.slope == 0)
                    sum++;
            }
        }
        int worst = (int)Math.pow(sum,2);

        bw.write(worst-best+" ");
        bw.close();
    }



    static boolean isSameParent(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            return false;
        return true;
    }
    static int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            parent[x] = y;
    }
}

class Edge implements Comparable<Edge>{
    int x, y, slope;

    Edge(int x, int y, int slope){
        this.x = x;
        this.y = y;
        this.slope = slope;
    }
    public int compareTo(Edge e){
        return e.slope - this.slope;
    }
}

Note

• slope=1, slope=0인 경우를 나눠 별도의 함수로 선언하고 메인함수에서 호출하는 식으로 구현했는데 실패. 입력 예제는 8이 도출됐지만, 제출 시 오답처리됨
• 입구->1번 따로 함수 구현, 출발은 항상 1번부터...처럼 놓친 조건이 있는지 계속 다시 읽고 구현했지만 좋은 방법이 아니었음