도시 분할 계획_1647

• 문제 : 도시 분할 계획
  • 간단 요약
  • 데이터
  • 접근법
    • MST 알고리즘
      • 프림 알고리즘
      • 크루스칼 알고리즘
    • 해결책
  • 코드

문제 : 도시 분할 계획

• 간단 요약

  마을에 여러 집들이 있는데, 경로별 유지비를 최소로 하면서, 마을을 2개로 나누고, 각 마을 내의 임의의 두 집들간 사이의 경로가 있게 해야 한다.

• 데이터

  	N	H	C
  의미	집의 개수	길의 개수	유지비
  범위	2 ~ 100,000	1 ~ 1,000,000	1,000

• 접근법

  문제 전체를 읽으면 핵심이 있는데,

  1. 분리된 마을 안의 임의의 두 집 사이에는 경로가 항상 존재해야 함
  2. 그러면서도 불필요한 길을 없앨 수 있음
  3. 나머지 길 유지비를 최소로

  결론적으로 두 집 사이에 불필요한 길이 없다는 건 사이클이 없다는 것

  그러면서 여러 길이 있지만 유지비를 최소로 하면서 마을을 연결하는 것

  => MST가 이에 부합한다.

  • MST 알고리즘

    • 프림 알고리즘

      프림 알고리즘은 정점을 기준으로 가장 가까운 정점을 연결하면서 진행한다.

      연결된 정점은 더 이상 탐색될 필요가 없기 때문에,
      탐색되지 않은 정점 중에서 현재 선택된 정점과 가장 가까운 경로의 정점을 찾아 다음 탐색 대상으로 정한다.

      기본적으로는 정점별 간선을 저장하는 리스트에 넣어두고서, 최소 정점을 찾아가며 반복할 수도 있지만,
      PQ를 이용하여 간선을 저장한다면 빠르게 가까운 정점을 확인할 수 있다.

    • 크루스칼 알고리즘

      크루스칼 알고리즘은 Union Find + Priority_Queue를 이용하여 가장 가중치가 적은 간선을 우선적으로 탐색하며 Cycle이 발생하지 않도록 정점들을 연결한다.

      모든 간선을 넣고, PQ가 Empty 상태가 될 때까지 하나씩 빼면서, 양 쪽 정점이 서로 다른 그룹일 경우 이를 하나로 통일하여 연결하는 것으로 한다.

  • 해결책

    본 포스팅에서는 크루스칼 알고리즘으로 풀이를 진행한다.

    문제는 간단하다.

    크루스칼로 하나의 마을로 MST를 구성한 다음, 해당 MST를 구성하는 간선들 중 가장 유지비가 많이 드는 간선 하나를 제거하면,
    MST는 사이클이 존재하지 않기 때문에, 해당 간선을 끊으면 관련된 정점으로 갈 수 있는 길이 사라지게 되어 자연스럽게 마을이 2개로 분리된다

• 코드

    // file: "BOJ_1647.cpp"
    #include <iostream>
    #include <climits>
    #include <tuple>
    #include <algorithm>
    #include <queue>
    #include <utility>    
    using namespace std;
  
    // 비용이 적은 순으로 정렬하기 위한 compare struct
    struct compare{
      bool operator()(tuple<int,int,int> a, tuple<int,int,int> b){
          return get<0>(a) >= get<0>(b);
      }
    };
  
    // 간선이 작은 것 먼저 나오도록 저장하는 priority-queue
    priority_queue<tuple<int,int, int>, vector<tuple<int,int,int>>, compare> pq;
    // 각 마을이 어느 그룹에 속해 있는지 체크하기 위한 배열
    int check[100001];
  
    // a번 마을의 그룹이 몇번인지 알려주는 함수
    int getHead(int a){
        if(check[a] != a){
            check[a] = getHead(check[a]);
        }
        return check[a];
    }
  
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        long long int n, m, lastNode = INT_MIN;
        long long sum = 0;
  
        cin >> n >> m;
  
        for(int i = 0; i < m; i++){
            int src, dst, cost;
            // 각 마을 1, 마을 2, 연결된 길의 유지비
            cin >> src >> dst >> cost;
            // 초기 그룹 번호를 자기 마을 번호로 설정
            check[src] = src;
            check[dst] = dst;
            // PQ에 정보 삽입
            pq.push({cost, src, dst});
        }
        // 간선이 다 빌 때까지 반법
        while(!pq.empty()){
            // 각 간선에 대한 유지비가 최대 1,000이고 간선 갯수가 1,000,000이므로 Int는 OverFlow가 날 가능성이 있음
            // 그걸 방지하기 위한 long long
            long long int cost, town1, town2;
            // pq에서 비용이 가장 적은 간선 cost, town1, town2에 대한 정보 추출
            tie(cost, town1, town2) = pq.top();
            // top에 있던 것 삭제
            pq.pop();
            // 서로 마을의 그룹 번호를 조회해서 같은 거면 이미 연결된 것이므로 진행하지 않음
            if(getHead(town1) == getHead(town2)){
                continue;
            }
            // 간선 총 비용에 더하기
            sum += cost;
            // 가장 비용이 큰 노드를 갱신함
            lastNode = max(lastNode, cost);
            // 각 마을이 속해있던 그룹을 통일
            check[getHead(town1)] = check[getHead(town2)];
        }
  
        // 모든 마을이 연결됐을 때의 비용에서 가장 유지비가 큰 간선을 제거한 것이 답
        cout << sum - lastNode;
  
    }