문제

도시 분할 계획

풀이

이전에 풀었는데, 끝까지 풀지 못했던 기억으로 다시 크루스칼 알고리즘을 정리해보았다

크루스칼 알고리즘은 최소 비용 알고리즘 중 하나로, 모든 간선이 연결되어있고 사이클 이 없는(한번 방문한 edge는 다시는 가지 않는) 알고리즘이다
이 알고리즘을 선택해야 하는 이유는 유지비를 최소로 하기 위함이고 시작 지점이 따로 주어지지 않았기 때문이다.

비용이 최소인 순서대로 정렬하기 위해서 House 객체를 선언하여 compareTo로 cost가 작은 순으로 정렬하여 담은 후에

이 배열에 다음과 같은 로직을 작성하도록 한다.

• edge가 방문한곳인지 확인하고
• edge 사이클이 발생하지 않는지 확인 하는 방식을 적용하면 된다

사이클 판별 법은 boolean 을 리턴으로 하는 판별식을 사용하면 되는 것 같은데, 여기서 parent 를 저장하는 배열을 따로 선언하여 getParent() 는 dfs를 사용하면 된다.

boolean[] parent = new parent[n + 1];

// x의 부모 edge를 리턴
private static int getParent(int x) {
	if (parent[x] == x) { // 사이클이 없는 자기자신
		return x;    
    }
    return parent[x] = getParent(parent[x]);
}

// 사이클 판별식
private boolean isNotCycle(int a, int b) {
	int x = getParent(a);
    int y = getParent(b);
    
    // 사이클이 아니다
    if (x != y) {
    	// y의 부모는 x이다 (부모 재정의)
    	parent[y] = x;
    	return true;
    } else { // 사이클 존재
    	return false;
    }
}

이 판별식들을 이용하여 가장 최소비용으로 정렬 후에 연결되지 않은 것들끼리 먼저 연결하는 방식을 사용한다. 내가 한번 틀렸던 부분이 여기서 존재 하는데

// 최소비용으로 정렬
Collections.sort(arr);

for (House h : arr) {
	if (isNotCycle(h.current, h.next)) {
    	if (count == n - 2) {
        	break;
        }
    	answer += h.cost; // 전체 비용 재정의
        count++;
        // 틀린 부분
        //if (count == n - 2) {
        //	break;
        //}
    }
}

count가 n - 2가 된 상태가 전부 이어졌다고 볼수 있기 때문에 멈춰주어야 하는데, 비용을 추가하기 전에 해야 해당 간선이 이어지기 전에 최소비용을 정의할 수있다. 여기서 방문여부를 확인하는 부분이 parent를 확인하여 count를 사용함으로서 대체되었다.

전체 코드

전체 코드