[JAVA] 백준 MST 뿌수기 1

 

최근에 MST를 공부해서 MST 뿌수기 시리즈를 해보려고 한다.

 

 

6497 전력난 - 골드4

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

6497번: 전력난

• 전체 간선의 길이가 최소가 되어야한다
  • 최소 스패닝 트리를 생각할 수 있음
• 그냥 최소스패닝 트리를 잘 만들면 되겠다.
• 길의 수가 적다고 정해져있지 않으니 크루스칼, 프림 아무거나 해도 될 것 같다.

 

Prim 알고리즘 풀이

class Node implements Comparable<Node> {
    int end;
    int distance;

    public Node(int end, int distance) {
        this.end = end;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(distance, o.distance);
    }
}

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int houseCnt = Integer.parseInt(st.nextToken());
            int roadCnt = Integer.parseInt(st.nextToken());

            if (houseCnt == 0) {
                break;
            }

            List<Node>[] arr = new ArrayList[houseCnt];
            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            int cost = 0;
            for (int i =0; i<roadCnt; i++) {
                st = new StringTokenizer(br.readLine());

                int house1 = Integer.parseInt(st.nextToken());
                int house2=  Integer.parseInt(st.nextToken());
                int distance= Integer.parseInt(st.nextToken());

                arr[house1].add(new Node(house2, distance));
                arr[house2].add(new Node(house1, distance));
                cost += distance;
            }

            PriorityQueue<Node> queue = new PriorityQueue<>();
            queue.add(new Node(0, 0));

            boolean[] visited = new boolean[houseCnt];
            int cnt = 0;
            int requiredCost = 0;

            while (!queue.isEmpty()) {
                Node currentNode = queue.poll();

                if (visited[currentNode.end])
                    continue;

                visited[currentNode.end] = true;
                cnt ++;
                requiredCost += currentNode.distance;

                if (cnt == houseCnt)
                    break;

                for (Node near: arr[currentNode.end]) {
                    if (visited[near.end])
                        continue;

                    queue.add(near);
                }
            }

            System.out.println(cost - requiredCost);
        }
    }
}

• 첫 prim알고리즘 풀이라서 풀이가 더럽다.

 

크루스칼 알고리즘 풀이

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int houseCnt = Integer.parseInt(st.nextToken());
            int roadCnt = Integer.parseInt(st.nextToken());

            if (houseCnt == 0)
                break;

            parent = new int[houseCnt];
            for (int i =1; i<parent.length; i++) {
                parent[i] = i;
            }

            PriorityQueue<int[]> pq= new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));

            int totalCost = 0;
            for (int i =0; i<roadCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int house1= Integer.parseInt(st.nextToken());
                int house2= Integer.parseInt(st.nextToken());
                int price= Integer.parseInt(st.nextToken());
                totalCost += price;

                pq.add(new int[]{house1, house2, price});
            }

            int cnt = 0;
            int cost = 0;
            while (cnt != houseCnt-1) {
                int[] poll = pq.poll();

                int parentA = find(poll[0]);
                int parentB = find(poll[1]);

                if (parentA == parentB) { //사이클 생김
                    continue;
                }

                union(parentA, parentB);
                cnt ++;
                cost += poll[2];
            }

            System.out.println(totalCost - cost);
        }
    }

    private static void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parent[parentY] = parentX;
        } else {
            parent[parentX] = parentY;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

• 그냥 전형적인 크루스칼 풀이다.

 

• 크루스칼이 프림보다 조금 더 빠르고 메모리도 적게 먹는다

 

 

13905 세부 - 골드4

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

13905번: 세부

• 그냥 최대 스패닝 트리를 구하려다가 멈칫했다
• 다익스트라 느낌으로 계속 갱신하면서 최대 가져갈 수 있는 빼빼로 개수를 구해야할 것 같았다.
• 그래서 다익스트라 느낌으로 풀었음

 

class Node implements Comparable<Node> {
    int end;
    int weight;

    public Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(o.weight, weight);
    }
}

public class Main {
    static List<Node>[] arr; //인접리스트

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

        int houseCnt = Integer.parseInt(st.nextToken());
        int bridgeCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[houseCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());

        int sung = Integer.parseInt(st.nextToken())-1; //숭이 위치
        int hye = Integer.parseInt(st.nextToken())-1; //혜빈이 위치

        for (int b= 0; b<bridgeCnt; b++) {
            st = new StringTokenizer(br.readLine());
            int house1 = Integer.parseInt(st.nextToken())-1;
            int house2 = Integer.parseInt(st.nextToken())-1;
            int weight = Integer.parseInt(st.nextToken());

            arr[house1].add(new Node(house2, weight));
            arr[house2].add(new Node(house1, weight));
        }

        int maxBB = solution(sung, hye);
        System.out.println(maxBB);
    }

    //최대 빼빼로 구하기, 다익스트라느낌?
    private static int solution(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(); //내림차순 정렬
        pq.add(new Node(start, Integer.MAX_VALUE));

        int[] minBebe = new int[arr.length]; //최소값으로 일단 초기화
        minBebe[start] = Integer.MAX_VALUE; //첫 번째 위치는 max값 초기화

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();

            if (currentNode.end == end) //혜빈이 도착하면 끝냄
                break;

            for (Node near: arr[currentNode.end]) {
                int min = Math.min(near.weight, currentNode.weight); //갱신될 값
                if (minBebe[near.end] < min) { //갱신될 값이 원래값보다크면
                    minBebe[near.end] = min; //갱신
                    pq.add(new Node(near.end, min)); //pq에 넣기
                }
            }
        }

        return minBebe[end];
    }
}

• 로직자체는 다익스트라와 아주 유사하다
• minBebe에 최대 가져갈 수 있는 빼빼로 개수를 저장한다
  • 출발 값은 max값으로 초기화한다
• Math.min(near.weight, currentNode.weight) 로 갱신될 값을 구해준다(이전 최댓값과 간선 weight의 최소값)
• 현재 값 minBebe[near.end] 보다 해당 값이 크면 갱신해주고 pq에 넣어주는 식으로 반복한다
• 혜빈이 node에 도착하면 while 문을 끝내고 해당 값을 return 한다

 

이 방법 말고도 최대스패닝 트리를 구하면 되지 않을까해서 구해봤다.

 

 

크루스칼 풀이

public class Main {
    static int[] parent;
    static int[] prev;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int houseCnt = Integer.parseInt(st.nextToken());
        int bridgeCnt = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int sung = Integer.parseInt(st.nextToken())-1; //숭이 위치
        int hye = Integer.parseInt(st.nextToken())-1; //혜빈이 위치

        int[][] lines = new int[bridgeCnt][3];
        parent = new int[houseCnt];
        for (int i =1; i< parent.length; i++) {
            parent[i] = i;
        }

        prev = new int[houseCnt];

        for (int b= 0; b<bridgeCnt; b++) {
            st = new StringTokenizer(br.readLine());
            int house1 = Integer.parseInt(st.nextToken())-1;
            int house2 = Integer.parseInt(st.nextToken())-1;
            int weight = Integer.parseInt(st.nextToken());

            lines[b] = new int[]{house1, house2, weight};
        }

        Arrays.sort(lines, (o1, o2) -> Integer.compare(o2[2], o1[2]));

        int result = 0;
        for (int i=0; i<lines.length; i++) {
            int[] tmp = lines[i];

            int parent1 = find(tmp[0]);
            int parent2 = find(tmp[1]);

            if (parent1 == parent2) {
                continue;
            }

            union(parent1, parent2);

            if (find(sung) == find(hye)) { //혜빈이와 숭이가 만나는 순간 !
                result = tmp[2];
                break;
            }
        }

        System.out.println(result);
    }

    static void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parent[y] = x;
        } else {
            parent[x] = y;
        }
    }

    static int find(int x) {
        if (x == parent[x])
            return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

• 프림알고리즘을 사용하면 50% 쯤에서 시간초과가 났고, 크루스칼 알고리즘은 겨우 통과하는 것 같다

• 다익스트라가 시간이 조금 덜 걸린다

 

 

 

16398 행성 연결 - 골드4

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

16398번: 행성 연결

• 그냥 mst를 구하고 최소비용을 구하면 된다
• 나는 크루스칼 방식을 사용하였다
• 입력배열은 주대각선 아래쪽만 받아서 간선으로 저장하였다.

 

public class Main {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        List<int[]> list = new ArrayList<>();

        for (int i =0; i<cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<i; j++) {
                int value = Integer.parseInt(st.nextToken());
                if (value != 0) {
                    list.add(new int[]{i, j, value});
                }
            }
        }

        parent = new int[cnt];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        Collections.sort(list, (o1, o2) -> {
            return Integer.compare(o1[2], o2[2]);
        });

        long result = 0;
        int lineCnt = cnt-1;
        for (int[] tmp: list) {
            if (lineCnt == 0)
                break;

            int parentA = find(tmp[0]);
            int parentB = find(tmp[1]);
            if (parentA == parentB)
                continue;

            result += tmp[2];
            union(parentA, parentB);
            lineCnt --;
        }

        System.out.println(result);
    }

    static int find(int x) {
        if (x == parent[x]) 
            return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parent[parentY] = parentX;
        } else {
            parent[parentX] = parentY;
        }
    }
}

 

 

 

 

21924 도시 건설 - 골드4

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

21924번: 도시 건설

• 이것도 mst를 구하면 된다
• long 타입을 사용해야한다는 걸 캐치해야함
• 전체 비용 - mst 비용을 빼주면 구할 수 있다
• 이번에도 크루스칼을 사용했다

 

public class Main {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int cnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());

        parent = new int[cnt];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        int[][] arr = new int[roadCnt][3];
        long totalPrice = 0;
        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a= Integer.parseInt(st.nextToken())-1;
            int b= Integer.parseInt(st.nextToken())-1;
            int value= Integer.parseInt(st.nextToken());
            arr[i] = new int[]{a,b,value};

            totalPrice += value;
        }

        Arrays.sort(arr, (o1, o2) -> {
            return Integer.compare(o1[2], o2[2]);
        });

        int remainCnt = cnt-1;
        long currentPrice = 0;
        for (int[] tmp: arr) {
            if (remainCnt == 0)
                break;

            boolean canUnion = union(tmp[0], tmp[1]);
            if (!canUnion)
                continue;

            remainCnt --;
            currentPrice += tmp[2];
        }

        if (remainCnt != 0)
            System.out.println(-1);
        else
            System.out.println(totalPrice - currentPrice);
    }

    static boolean union(int x, int y) {
        if (x == y)
            return false;

        int parentX= find(x);
        int parentY = find(y);

        if (parentX == parentY)
            return false;

        if (parentX < parentY)
            parent[parentY] =parentX;
        else
            parent[parentX] =parentY;

        return true;
    }

    static int find(int x) {
        if (x == parent[x])
            return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

 

 

 

 

1414 불우이웃돕기 - 골드3

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

1414번: 불우이웃돕기

• mst를 구하면 되는 쉬운 문제지만 입력값때문에 골드3으로 들어온 것 같다
• 이번에도 크루스칼을 사용하겠다!

 

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        List<int[]> lines = new ArrayList<>();
        int total = 0;

        parent = new int[cnt];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        for (int i=0; i<cnt; i++) {
            String input = br.readLine();

            for (int j=0; j<cnt; j++) {
                char c = input.charAt(j);
                if (c == '0')
                    continue;

                int length;
                if (c > 'Z') {
                    //소문자면
                    length = c - 'a' + 1;
                } else {
                    //대문자면
                    length = c - 'A' + 27;
                }

                lines.add(new int[]{i, j, length});
                total += length;
            }
        }

        Collections.sort(lines, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        int lineCnt = cnt-1;;
        for (int[] tmp : lines) {
            if (lineCnt == 0) {
                break;
            }

            boolean canUnion = union(tmp[0], tmp[1]);
            if (!canUnion)
                continue;

            lineCnt--;
            total -= tmp[2];
        }

        if (lineCnt != 0) {
            System.out.println(-1);
        } else {
            System.out.println(total);
        }
    }

    private static boolean union(int x, int y) {
        if (x == y)
            return false;

        int parentX = find(x);
        int parentY = find(y);

        if (parentY == parentX) {
            return false;
        }

        if (parentX < parentY) {
            parent[parentY] = parentX;
        } else {
            parent[parentX] = parentY;
        }

        return true;
    }

    private static int find(int x) {
        if (x == parent[x])
            return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

• 대문자, 소문자일 때만 잘 고려해서 간선값을 넣어주면 어렵지 않게 풀린다

 

 

 

 

1774 우주신과의 교감 - 골드3

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

1774번: 우주신과의 교감

• 모든 우주신, 황선자씨는 연결되어야함 -> 신장트리
  • 그 합이 최소가 되어야함 -> 최소 신장트리
• 이번에도 크루스칼을 사용하려고 한다.
  • 첫 번째 설계 - 틀림 
    • 일단 이미 연결된 애들을 union해준다
    • 연결된 적 없는 우주신들을 표시해서 해당 우주신과 다른 모든 우주신, 황선자씨의 거리를 구한 뒤에 pq에 넣는다
    • pq에서 하나씩 빼면서 union을 반복해줌
    • node개수 -1 만큼 간선이 선택되면 break
  • 틀린 이유: 나는 황선자씨와 연결된 우주신들이 잘은 mst로 주어지는 줄 알았는데, 그냥 황선자씨와 관련없는 우주신들끼리도 연결이 가능했다;;; 문제 이해를 잘못했었다
  • 모든 거리에 대한 조합을 구해서 제출하니 맞았습니다가 나왔다.
• +) 질문 게시판을 찾아보니 이미 연결된 node가 중복으로 나올 수도 있었다. (이거 때문에 틀리신 분들은 진짜 짜증날 것 같다...) 자꾸 이유없이 틀리신 분들은 참고하시길

 

class Node implements Comparable<Node> {
    int a;
    int b;
    double distance;

    public Node(int a, int b, double distance) {
        this.a = a;
        this.b = b;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        return Double.compare(this.distance, o.distance);
    }
}

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int godCnt = Integer.parseInt(st.nextToken());
        int existsCnt = Integer.parseInt(st.nextToken());

        int[][] locations = new int[godCnt][2];
        parent = new int[godCnt];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        for (int i =0; i<godCnt; i++) {
            st = new StringTokenizer(br.readLine());
            locations[i][0] = Integer.parseInt(st.nextToken());
            locations[i][1] = Integer.parseInt(st.nextToken());
        }

        double sum = 0;
        int remainCnt = godCnt-1;
        for (int i =0; i<existsCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;

            boolean isConnect = union(x, y);
            if (!isConnect)
                continue;

            remainCnt--;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (int i =0; i<locations.length; i++) {
            for (int j=i+1; j<locations.length; j++) {
                if (i == j)
                    continue;

                double distance = getDistance(locations[i][0], locations[i][1], locations[j][0], locations[j][1]);
                pq.add(new Node(i, j, distance));
            }
        }

        while (!pq.isEmpty()) {
            if (remainCnt == 0)
                break;

            Node currentNode = pq.poll();
            boolean isConnect = union(currentNode.a, currentNode.b);
            if (!isConnect) {
                continue;
            }

            double distance = getDistance(locations[currentNode.a][0], locations[currentNode.a][1], locations[currentNode.b][0], locations[currentNode.b][1]);
            sum += distance;
            remainCnt--;
        }

        System.out.println(String.format("%.2f", sum));
    }

    private static double getDistance(int x1, int y1, int x2, int y2) {
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }

    private static boolean union(int x, int y) {
        if (x == y)
            return false;

        int parentX = find(x);
        int parentY = find(y);
        if (parentY == parentX)
            return false;

        if (parentX < parentY) {
            parent[parentX] = parentY;
        } else {
            parent[parentY] = parentX;
        }

        return true;
    }

    private static int find(int x) {
        if (x == parent[x])
            return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

• 그냥 크루스칼만 잘 돌려주면 된다