BOJ_1647 : 도시 분할 계획

👉 문제링크

1647번: 도시 분할 계획

---

🔸 문제 분석 🔸

• N개의 집과 M개의 집 사이를 연결하는 길이 있다.
• 서로 이어지지 않는 마을 2개를 만드려고 하는데, 각 마을 안에서는 집끼리 길이 연결되어 있어야 한다.
• 길의 유지비 합의 최소값을 출력한다.

🔸 문제 풀이 🔸

• 마을 안에서 집 사이에 길이 연결되어 있어야 하고, 그 가중치가 최소가 되어야 하므로, 두 개의 최소 신장 트리(MST) 가 만들어져야 한다.
• 여기서는 크루스칼(Kruskal) 알고리즘을 사용했다. 
  • 간선을 모두 입력받고, 유지비 기준으로 오름차순 정렬한다.
  • 차례로 집합을 합칠 수 있는지 Union-Find로 확인하며, 집합이 2개가 될 때까지 반복한다.
• 최종 누적 유지비를 출력한다.

🔸 코드 🔸

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    private static int[] parent;

    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 = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        if (N == 2) {
            bw.write("0");
            bw.flush();
            return;
        }

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

        Edge[] edges = new Edge[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(edges, Comparator.comparing(o -> o.cost));

        long answer = 0;
        int set = N;
        for (Edge e : edges) {
            if (union(e.start, e.end)) {
                set--;
                answer += e.cost;
            }

            if (set == 2) break;
        }

        bw.write(Long.toString(answer));
        bw.flush();
    }

    private static boolean union(int a, int b) {
        int ap = find(a);
        int bp = find(b);

        if (ap == bp) {
            return false;
        } else {
            parent[bp] = ap;
            return true;
        }
    }

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

    private static class Edge {
        int start, end, cost;

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

🔸 코드 해석 🔸

• 집의 개수 N과 간선의 개수 M을 입력받는다. N이 2이면 간선의 수 상관 없이 0을 출력한다.
• Union-Find에서 집합 확인을 위한 부모 인덱스 저장 배열 parent를 만들어 인덱스를 값으로 초기화한다.
• 두 인덱스와 유지비를 저장 할 간선 클래스 Edge를 만들어 값을 초기화한다.
• Edge배열 edges를 유지비 기준으로 오름차순 정렬한다.
• 각 간선을 오름차순으로 확인하며, 집합이 합쳐지면 집합 개수 set을 -1하고 유지비를 answer에 누적한다.
• 최종 answer을 출력한다.

---

🔸 end 🔸

• 처음에 97%에서 틀려서 answer가 int가 아니라 long이어서 그런가하고 고쳤지만 여전히 틀렸다.
  • answer의 최대값은 10억으로 int로 가능하다고 계산했었는데, 아니나 다를까 이상없었다.
  • 틀린 원인은 n이 2일 때는 union이 필요없는데, 코드는 무조건 한 번 union이 이루어 지도록 만들었기 때문이다.
• lowcase를 확인하려고 1 2 / 1 2 3 입력을 했었는데, 바보같이 3이 나온걸 확인하고 이상이 있는지 몰랐다.
  • 0이 나와야 정상이었고, 틀린 이후에 질문 게시판을 보고 깨달았다.
  • 뭔가 다른 이유가 있을거라고 생각하고, 직접 계산하고 테스트한 케이스를 간과한게 부끄럽다.
  • 질문 게시판을 보기전에 더더욱 꼼꼼하게 검사하는 버릇을 들여야겠다. 조금 시건방진 테도였던 것 같다.
• 웃긴건 '아 이거 2개 집합 나눠서 확인해야 하니까, 정렬하고 Union-Find' 쓰면 되겠다' 하고 문제 풀이한 뒤 질문게시판에 MST, 크루스칼, 프림 얘기가 나와서 왜 그렇게 풀이하지? 하고 의문을 갖었다.
  • 알고보니 내 풀이가 크루스칼이었다...너무 자연스럽게 생각했는데 MST 알고리즘 이론이 많이 빈약하다는걸 다시 한번 깨달았다.
• 이번엔 알고리즘 풀이 계획을 적어가며 풀이했다.