[백준] No.1944 - 복제 로봇 (C++, 크루스칼 MST)

문제

 

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

1944번: 복제 로봇

 

풀이

 

solved.ac 난이도: Gold 2

 

 

BFS를 이용하여 떨어진 열쇠들과 시작 위치의 최단 거리를 구하여 간선으로 이어준다음, 최소 스패닝 트리(Minimum Spanning Tree)를 구하는 문제.

 

문제가 약간 특이한 편이지만 잘 읽어보면 로봇은 결국 열쇠들로 이동할 때는 최단 경로(거리)로 이동하는 것이 항상 최선의 방법임을 알 수 있다.

열쇠나 시작 위치에서는 로봇이 복제가 되는 것은 현재 위치에서 두 개 이상의 정점으로 이동할 때만 의미가 있다.

즉, 현재 정점(열쇠나 시작 위치)에서 다른 정점으로 이동하는 개수 만큼의 로봇을 복제하면 된다.

(사실 움직인 횟수의 총합이 중요하기 때문에 로봇을 얼마나 복제하든 정점에 멈춰있으면 상관없다.)

결국 그래프에서 최소 스패닝 트리를 구하면 시작 위치에서 다른 모든 정점으로의 이동하는 것이 가능하고,

최소 스패닝 트리에 의해 총 움직인 횟수 (= 트리의 모든 간선의 가중치 합)를 최소로 만들 수 있다.

 

 

일단 정점들을 서로 연결하기 위해서 해당 정점에서부터 BFS를 진행하여 다른 정점으로의 최단 거리를 가중치로 하는 간선을 설정하자.

 

pair<int,int> convert_idx2pos[251];
int convert_pos2idx[50][50];
 
struct Vertex{
  int r, c, depth;
};
 
bool ConnectEdgeBFS(int start_r, int start_c){
  queue<Vertex> q;
  bool is_in_que[50][50];
  memset(is_in_que, false ,sizeof(is_in_que));
 
  int start_idx = convert_pos2idx[start_r][start_c];
  int cnt_vertex = 0;
 
  q.push({start_r, start_c,0});
  is_in_que[start_r][start_c] = true;
 
  int r,c, next_r, next_c, next_depth, next_idx;
  while(!q.empty()){
    r = q.front().r;
    c = q.front().c;
    next_depth = q.front().depth + 1;
    q.pop();
 
    for(int i=0; i<4 ; ++i){
      next_r = r + change_pos[i][0];
      next_c = c + change_pos[i][1];
 
      //범위 확인
      if(next_r <0 || maze_size <= next_r || next_c<0 || maze_size<= next_c)
        continue;
      //이미 큐에 삽입된 적 있다면 패스
      if(is_in_que[next_r][next_c] || maze_map[next_r][next_c] == '1')
        continue;
      
      q.push({next_r, next_c, next_depth});
      is_in_que[next_r][next_c] = true;
      
      if(maze_map[next_r][next_c] == 'K' || maze_map[next_r][next_c] == 'S'){
        next_idx = convert_pos2idx[next_r][next_c];
        dist[start_idx][next_idx] = next_depth;
        ++cnt_vertex;
      }
    }
 
  }
 
  return cnt_vertex == key_num;
}

 

 

이제 최소 스패닝 트리를 구하는 알고리즘인 크루스칼 알고리즘을 이용하여 답을 구하자.

구현 시에 각각의 열쇠('K')나 시작 정점('S')을 배열에 저장하여 나타내기 위해 번호를 부여한 후 위치 값과  번호 값을 변환할 수 있도록 다음 배열들을 이용하자.

pair<int,int> convert_idx2pos[251];

정점의 번호[idx]를 위치 값(r, c)로 변환

 

int convert_pos2idx[50][50];

정점의 위치 값[r][c]을 번호로 변환

 

이런 식의 좌표값을 번호로 변환하는 과정이 필요한 이유는 크루스칼 알고리즘은 분리 집합(Union-Find 자료구조)을 이용해서 구현해야 하기 때문이다. 

 

class DisjointSet{  // Union find 구현
  public:
  vector<int> parent, rank;
 
  DisjointSet(int n): parent(n), rank(n){
    for(int i=0; i<parent.size() ; ++i) //초기는 자신이 루트
      parent[i] = i;
  }
 
  int Find(int u){
    if(parent[u] == u)
      return u;
    return parent[u] = Find(parent[u]);
  }
 
  void Union(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v)
      return;
 
    if(rank[v] < rank[u]) //rank는 항상 v가 크게 유지
      swap(u,v);  
 
    parent[u] = v;  //u를 v의 하위로 Union
    if(rank[u] == rank[v])
      rank[v]++;
 
    return;
  }
};

 

 

크루스칼 알고리즘은 그래프의 모든 간선의 정보(두 정점과 간선의 가중치)를 정렬하여 가장 작은 가중치의 간선부터 이어나가기 시작한다.

따라서 간선의 개수 E에 지배적이기 때문에 간선이 비교적 적은 그래프일 수록 크루스칼 알고리즘이 효과적이다.

반면에 거의 모든 정점들이 서로 연결된 밀집 그래프의 경우 정점의 개수 V에 지배적인 MST 알고리즘인 프림 알고리즘이 효과적이다.

추천 문제: [알고스팟] LAN - 근거리 네크워크

 

(단, 이번 문제는 밀집 그래프이지만 정점의 개수가 많지 않아 크루스칼 알고리즘으로 구현하였습니다.)

 

 

struct Edge{
  int u, v, weight;
 
  bool operator<(const Edge& x){
    return weight < x.weight;
  }
};
 
int Kruskal(){
  int min_spanning=0;
  vector<Edge> edges;
  
  for(int u=0; u<=key_num ; ++u){
    for(int v=0; v<=key_num ; ++v){
      if(u==v)
        continue;
      edges.push_back({u,v, dist[u][v]});
    }
  }
 
  sort(edges.begin(), edges.end());
 
  DisjointSet sets(key_num+1);  //초기에는 모두 독립 집합
 
  int u, v, weight;
  for(int i=0; i<edges.size() ; ++i){
    u = edges[i].u; v = edges[i].v;
    weight = edges[i].weight;
 
    if(sets.Find(u) == sets.Find(v))  //이미 합쳐진 경우
      continue;
 
    sets.Union(u, v); //간선을 이었으므로 유니온
    min_spanning += weight;
 
  }
 
  return min_spanning;
}

 

 

 

 

코드