Boj 11991. Fenced in

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

 

USACO 문제입니다 그리고 재밌는 문제입니다.

 

아이디어가 중요한 문제인데 이 문제를 풀 기 위해선 Disjoint-set 개념을 살짝만 가지고 있으면 됩니다.

$(N+1)*(M+1)$ 의 방이 있고 상하좌우 벽들을 잘 뿌셔서 모든 방이 연결되게 하는데 뿌시는 벽의 길이를 최소화 시키는 문제입니다.

 

즉 $(N+1)*(M+1)$ 의 정점을 만들고 인접한 정점끼리의 가중치를 사이에 있는 벽의 길이로 하고 크루스칼을 돌리면 됩니다.

 

엇! 하지만 $N$ $M$ 이 둘다 25000이네요 무조건 터질 것이 예상되기에 더 줄여봅시다.

 

조금 생각을 해보면 크루스칼의 원리에 따라 작은 가중치부터 처리될 것이라는 것이 명백합니다.

즉 어떠한 행이나 열을 한 번에 다 부셔버리는 것이 크루스칼의 원리에 위배가 되지 않는 것이죠. 

 

즉 우리는 어떤 행이나 열을 다 부셔버리는 것을 어떻게 해야 최적인지를 판단하면 됩니다.

 

각 행이나 열을 다 부셔버리면 그 행이나 열은 다 같은 집합에 속하게 됩니다.

 

그리고 같은 집합에 속하게 되면 부술 때 부숴야 되는 벽의 개수가 줄게 됩니다.

 

즉 최대한 같은 집합에 속하게 하는게 무조건 이득이라는 것을 알 수 있습니다.

 

근데 여기서 주목해야 될 것은 하나의 행 또는 하나의 열이 부셔지지 않으면 행과 열은 절대 같은 집합에 속해지지 않습니다.

 

즉 우리는 가장 작은 가중치를 가진 행과 열을 먼저 부숴놓고 그 다음으로는 행 열 구분 없이 가중치가 작은 것 부터 그리디하게 부숴주면 되겠습니다.

 

그럼 시간복잡도는 $O(N*logN + M*logM)$ 이 됩니다.