(17472) 다리 만들기 2

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

단계별로 풀어보기

35단계(최소 신장 트리) 6번째

 

 

 

정점과 간선을 구하는 것이 매우 복잡하다는 점만 빼면, 평범한 MST 문제다.

섬의 개수가 최대 6개이므로 유니온 파인드는 하드코딩으로 전처리 했다.

정점과 간선을 구하는 과정은 구현, 시뮬레이션 파트에 가까우니 생략한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int, int>> edge;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector board(n+2, vector<int> (m+2));
  
  vector<int> uf= {0, 1, 2, 3, 4, 5, 6, 7};
  vector<edge> v;
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin >> board[i][j];
    }
  }
  
  auto dfs= [&](auto self, int x, int y, int t) -> void {
    board[x][y]= t;
    
    if(board[x-1][y]==1)  self(self, x-1, y, t);
    if(board[x+1][y]==1)  self(self, x+1, y, t);
    if(board[x][y-1]==1)  self(self, x, y-1, t);
    if(board[x][y+1]==1)  self(self, x, y+1, t);
  };
  
  int num= 1;
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(board[i][j]==1){
        dfs(dfs, i, j, ++num);
      }
    }
  }
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(board[i][j]){
        int len=0;
        while(1){
          len++;
          if(i==len)  break;
          
          if(board[i-len][j]){
            if(len>2){
              v.push_back({len-1,{board[i][j],board[i-len][j]}});
            }
            break;
          }
        }

        len=0;
        while(1){
          len++;
          if(j==len)  break;
          
          if(board[i][j-len]){
            if(len>2){
              v.push_back({len-1,{board[i][j],board[i][j-len]}});
            }
            break;
          }
        }
      }
    }
  }
  
  sort(v.begin(), v.end());
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    if(x==y)  return false;
    
    uf[y]= x;
    
    return true;
  };
  
  int cnt= 1, ans= 0;
  
  for(edge elem:v){
    if(merge(elem.second.first, elem.second.second)){
      cnt++;
      ans+= elem.first;
      
      if(cnt==num-1)  break;
    }
  }
  
  cout << (cnt==num-1 ? ans : -1);
  
  return 0;
}