[ 백준 ] 1647 도시 분할 계획

Link | 1647번 문제 : 도시 분할 계획

📌 About

문제에서 요구하는 것은 두 구역으로 쪼갠 마을의 최소 유지 비용을 구하는 것이다.

여기서 MST를 구하면 된다는 것을 떠올릴 수 있다. 간단히 kruskal algorithm을 사용하면 된다.

다만, 이 때 두 구역은 연결이 되어 있지 않는다.

즉, 간선의 개수는 집의 개수 - 2이며 MST에서 최대 비용 간선만 제거하면 된다.

Kruskal algorithm에서는 최소 비용 간선부터 탐색한다.

그렇기 때문에 추가한 간선의 개수가 집의 개수 - 2가 될 때까지만 탐색을 하면 된다.

Kruskal Algorithm...?

📌 Solution

📍 Step 0. 간선 정보 class 구현

간선의 정보를 Road class으로 만든다.

class Road implements Comparable<Road> {

    int homeA, homeB, cost;

    public Road(int homeA, int homeB, int cost) {
        this.homeA = homeA;
        this.homeB = homeB;
        this.cost = cost;
    }

    @Override
    public int compareTo(Road road) {
        return cost - road.cost;
    }
}

이 때 우리는 간선을 오름차순으로 정렬해야 하기 때문에 Comparable을 구현한다.

📍 Step 1. 필요 자료구조 선언

Kruskal algorithm에서는 각 정점의 root 정점 정보와 간선 list가 필요하다.

간선들은 오름차순으로 탐색할 것이기 때문에 priority queue를 사용한다.

private int[] roots;
private final Queue<Road> roads = new PriorityQueue<>();

📍 Step 2. Read

주어진 정보를 읽어 값을 저장한다.

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int homeNum = Integer.parseInt(tokenizer.nextToken());
    int roadNum = Integer.parseInt(tokenizer.nextToken());

    roots = IntStream.rangeClosed(0, homeNum).toArray();
    while (roadNum-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int homeA = Integer.parseInt(tokenizer.nextToken());
        int homeB = Integer.parseInt(tokenizer.nextToken());
        int cost = Integer.parseInt(tokenizer.nextToken());
        roads.offer(new Road(homeA, homeB, cost));
    }
}

📍 Step 3. Kruskal Algorithm

초기화까지 완료되었다면 알고리즘을 실행한다.

이때 위에서 말한 것처럼 선택하는 간선의 수는 집의 수 - 2이다.

마지막으로 반환된 weight 값을 출력하면 된다.

private int divideCity() {
    int weight = 0, count = 0;
    while (!roads.isEmpty() && count != roots.length - 3) {
        Road road = roads.poll();
        int rootA = find(road.homeA);
        int rootB = find(road.homeB);
        if (rootA != rootB) {
            weight += road.cost;
            count++;
            union(rootA, rootB);
        }
    }
    return weight;
}

📌 Code

GitHub Repository

class Road implements Comparable<Road> {

    int homeA, homeB, cost;

    public Road(int homeA, int homeB, int cost) {
        this.homeA = homeA;
        this.homeB = homeB;
        this.cost = cost;
    }

    @Override
    public int compareTo(Road road) {
        return cost - road.cost;
    }
}

private int[] roots;
private final Queue<Road> roads = new PriorityQueue<>();

public void solve() throws IOException {
    init();
    int weight = divideCity();
    result.append(weight);
}

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int homeNum = Integer.parseInt(tokenizer.nextToken());
    int roadNum = Integer.parseInt(tokenizer.nextToken());

    roots = IntStream.rangeClosed(0, homeNum).toArray();
    while (roadNum-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int homeA = Integer.parseInt(tokenizer.nextToken());
        int homeB = Integer.parseInt(tokenizer.nextToken());
        int cost = Integer.parseInt(tokenizer.nextToken());
        roads.offer(new Road(homeA, homeB, cost));
    }
}

private int divideCity() {
    int weight = 0, count = 0;
    while (!roads.isEmpty() && count != roots.length - 3) {
        Road road = roads.poll();
        int rootA = find(road.homeA);
        int rootB = find(road.homeB);
        if (rootA != rootB) {
            weight += road.cost;
            count++;
            union(rootA, rootB);
        }
    }
    return weight;
}

private void union(int homeA, int homeB) {
    if (homeA < homeB) roots[homeB] = homeA;
    else roots[homeA] = homeB;
}

private int find(int road) {
    return road == roots[road] ? road : find(roots[road]);
}