백준 1647번 - 도시 분할 계획

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

1647번: 도시 분할 계획

최근 최소스패닝트리(MST)를 공부했었기 때문에 어려운 문제가 아니었지만 예외처리를 해주거나 살짝 다르게 생각해볼 여지가 있기 때문에 기록에 남긴다.

 

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

class Home {
    int v1, v2, cost;
    Home(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
}

public class Main {
    static int answer;
    static ArrayList<Home> arr;
    static int n, m;
    static int[] unf;
    public static int Find(int v) {
        if(v == unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }
    public static void Union(int a, int b) {
        int fa = Find(a);
        int fb = Find(b);
        if(fa != fb) unf[fa] = fb;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        unf = new int[n+1];
        for(int i=1; i<=n; i++) unf[i] = i;
        arr = new ArrayList<>();
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            arr.add(new Home(a, b, c));
        }
        Collections.sort(arr, (o1, o2) -> {
            return o1.cost - o2.cost;
        });
        int cnt = 0;
        for(Home ob : arr) {
            int fa = Find(ob.v1);
            int fb = Find(ob.v2);
            if(fa!=fb) {
                answer += ob.cost;
                Union(ob.v1, ob.v2);
                cnt++;
                if(cnt == n-2) break;
            }
        }
        
        System.out.println(answer);
    }
}

 

문제의 요구조건에 따르면 모든 집이 연결되는게 아닌, 두 개의 마을 속 각각의 집들끼리만 연결되도록 해야한다. 즉 최소스패닝트리(MST)를 완성하는데에 필요한 n-1개의 간선이 아닌 하나 부족한 n-2개의 간선으로 트리를 구성하면된다. 그렇게 되면 간선이 하나 부족한 트리가 완성되고 자연스레 두 그룹으로 각각 새로운 트리로 나뉘어지게 된다.

따라서 위와 같이 cnt를 세면서 n-2개의 간선을 완성했을때 break 조건을 걸었고 충분히 정답인 코드로 보여진다.

하지만 제출했을때 틀렸다고 나와서 당황했고 한참동안 이유를 찾을 수가 없었다.

그리고 위와 같은 코드는 n이 가장 작은 2일때 만족하지 않음을 찾을 수가 있었다.

n=2일때는 무조건 두 마을 각각에 하나의 집만 존재하게 되고 간선이 존재하지 않는다. 하지만 위 코드의 경우 일단 cost를 answer에 더하고 if조건을 통해 break를 하기 때문에 0이 나와야할 답이 0이 아니게 출력되는 것이다.

따라서 n=2일때 예외처리를 해주든지, n-1 일때 break을 하고 가장 나중 간선의 cost를 빼주든지 하는 방법으로 다시 풀어보니 정답 처리가 되었다.

 

 

1.  n = 2 경우 예외 처리

 

int cnt = 0;
for(Home ob : arr) {
    int fa = Find(ob.v1);
    int fb = Find(ob.v2);
    if(fa!=fb) {
        answer += ob.cost;
        Union(ob.v1, ob.v2);
        cnt++;
        if(cnt == n-2) break;
    }
}
if(n==2) answer = 0;
System.out.println(answer);

 

 

2. n - 1 break 후 가장 큰 cost 빼주기

 

int cnt = 0;
int bigCost = 0;
for(Home ob : arr) {
    int fa = Find(ob.v1);
    int fb = Find(ob.v2);
    if(fa!=fb) {
        answer += ob.cost;
        Union(ob.v1, ob.v2);
        bigCost = ob.cost;
        cnt++;
        if(cnt == n-1) break;
    }
}
System.out.println(answer-bigCost);

 

만약 2번처럼 다른 방식을 생각해내지 못한다면 1번처럼 예외처리를 잘해줘야한다.

아무리 봐도 풀이가 맞는 것 같고 다른 방법이 생각나지 않는 답이 없는 상황이라면 예외처리를 제대로 해줬는지 확인해보자. 의외로 이번 문제와 같이 실마리를 찾을 수 있을지도 모른다.

다른 풀이를 생각해내는 것도 중요하지만, 이번 문제를 통해 무엇보다 예외처리가 중요하다는 것, 특히 가장 작은 첫 입력값일때를 주의해야 함을 깨달았다.