백준 1143번: 경찰 (C++)

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

1143번: 경찰

---

Solved By: SCC

 

몇 달 전 이 문제를 시도했을 때와 이번에 시도했을 때 막혔던 부분의 코드를 비교해보니 똑같더군요. 하지만, 이번엔 관점을 좀 다르게 잡았습니다. SCC 코드에 문제가 있는 게 아닐까 싶어 코드를 뜯어보던 반면 이번엔 이전부터 같은 SCC 코드를 사용하는데 뭐가 문제겠냐 싶어서 평균값에 초점을 두었습니다.

 

이 문제를 푸는 방법은 SCC를 통해 어느 한 SCC의 indegree가 0이라면 그 SCC 안에서 최솟값을 가지는 경찰서 설치비용을 무조건 하나 가져와야 합니다. indegree가 1 이상이라면 다른 SCC에서 경찰이 올 수 있다는 뜻이기 때문에 필요 없습니다. 사용하지 말라는 것이 아니라 사용해도 되고 안 해도 됩니다. 사용하지 말라는 것이 아니라는 게 중요합니다. 또한, indegree가 0인 SCC에서 최솟값이 아닌 다른 노드에서도 평균값의 최솟값이 나오도록 한다면 그 노드의 비용도 사용해도 됩니다.

 

즉, 필수 노드(indegree 0 SCC의 최솟값을 가지는 노드)를 제외한 모든 노드들이 가용한 노드들입니다.

 

2번째로 중요한 포인트는 하나의 케이스를 가지고 설명해보겠습니다.

indegree가 0인 두 개의 SCC에서 최솟값을 3, 3을 가져왔다고 하고, 다른 노드에서 비용을 3, 1을 가져왔다고 합시다.

 

평균값이 최솟값이 되게끔 하는 것이니까 indegree 0 SCC에서 이미 6까지 더하고 2를 나누어 평균값을 구할 수 있습니다. 하지만, 다른 노드에서 차례대로 더하여 평균을 구했을 때, 기존의 평균값보다 더 작은 값이 구해진다면 해당 값을 채택해야 합니다. 위에서 말한 케이스에서 다음과 같은 사례를 발견할 수 있습니다.

 

사례는 두 가지로 나누어 볼 수 있습니다.

1) indegree_0 = {3, 3}, other_nodes = {3, 1}

2) indegree_0 = {3, 3}, other_nodes = {1, 3}

 

1번의 경우 (3+3)/2 = 3에서 other_nodes의 값들을 순차적으로 하나씩 더해가면 (3+3+3)/3 = 3, (3+3+3+1)/4 = 2.5로 평균값의 최솟값은 2.5로 결론됩니다. 하지만, 이게 맞는지 의구심이 들 수 있습니다. 2번의 경우를 봅시다.

 

2번의 경우 (3+3)/2 = 3에서 other_nodes의 값들을 순차적으로 하나씩 더해가면 (3+3+1)/3 = 2.3333..., (3+3+1+3)/4 = 2.5으로 2.5가 되기 전, 2.3333... 이 최솟값이라는 것을 알 수 있습니다.

 

여기서 알 수 있는 건 indegree가 0인 SCC에서 최솟값을 가져온 노드를 제외한 나머지 노드들은 오름차순으로 정렬이 되어있고, 순차적으로 나머지 값들을 탐색하여 평균값이 낮아지지 않는다면 더할 필요가 없는 것입니다.

---

풀이 과정이 꽤 길었는데 핵심을 3가지로 추려 설명하면

1. indegree가 0인 SCC에서 최솟값을 가지는 비용은 무조건 평균값을 구성하는 값으로 들어가야 한다.
2. 필수 노드를 제외한 모든 노드들은 평균값을 구성하는 노드로써 조건이 성립한다.
3. 필수 노드를 제외한 나머지 노드의 비용들은 오름차순으로 정렬되어 평균값을 구해주며 더 이상 감소하지 않을 때까지 평균값을 구성하는 노드로 채택해야 한다.

#include <iostream>
#include <vector>
#include <stack>
#include <memory.h>
#include <algorithm>
#define MAX 50
using namespace std;

int N;
vector<int> adj[MAX];
vector<vector<int>> SCC;
int visitedOrder[MAX];
int sccnum[MAX]; // node들이 어떤 SCC에 속해있는지 확인
int indegree[MAX]; // SCC area node끼리의 indegree를 고려함
stack<int> s;
int order = 0;
int sccCnt = 0;
vector<double> cost;

int dfs(int now){
    int parent = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){ // 방문하지 않았다면
            parent = min(parent, dfs(next));
        }
        else if(sccnum[next] == -1){
            // SCC parent 갱신?
            parent = min(parent, visitedOrder[next]);
        }
        else{
            // 이미 SCC로 구성된 노드에 진입을 하려한다면
            // 해당 SCC의 진입차수가 하나 커진다.
            indegree[sccnum[next]]++;
        }
    }
    
    if(parent == visitedOrder[now]){
        vector<int> scc;
        while(1){
            int temp = s.top(); s.pop();
            sccnum[temp] = sccCnt;
            scc.push_back(temp);
            if(temp == now) break;
        }
        SCC.push_back(scc);
        
        if(!s.empty()) ++indegree[sccCnt];
        ++sccCnt;
    }
    
    return parent;
}

void tarjan(){
    memset(visitedOrder, -1, sizeof(visitedOrder));
    memset(indegree, 0, sizeof(indegree));
    memset(sccnum, -1, sizeof(sccnum));
    order = 0, sccCnt = 0;
    
    if(!s.empty()) s.pop();
    
    for(int i = 0; i < N; i++){
        if(visitedOrder[i] == -1) dfs(i);
    }
}

pair<int, double> minValue_withNode(vector<int>& scc){
    double ret = 1000; // cost의 최솟값
    int node = 0; // 해당 cost의 node
    for(int i = 0; i < scc.size(); i++){
        if(cost[scc[i]] < ret){
            ret = cost[scc[i]];
            node = scc[i];
        }
    }
    return {node, ret};
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    cost.resize(N);
    for(int i = 0; i < N; i++){
        cin >> cost[i];
    }
    
    for(int i = 0; i < N; i++){
        string adjS; cin >> adjS;
        for(int j = 0; j < adjS.length(); j++){
            if(adjS[j] == 'Y'){
                adj[i].push_back(j);
            }
        }
    }
    
    tarjan();
    
    double pCnt = 0;
    double pSum = 0;
    
    for(int i = 0; i < sccCnt; i++){
        if(indegree[i] == 0){ // 무조건 경찰서를 설치해야 하는 경우
            auto node_and_value = minValue_withNode(SCC[i]);
            ++pCnt;
            pSum += node_and_value.second;
            cost[node_and_value.first] = -1;
        }
    }
    
    sort(cost.begin(), cost.end());
    
    for(int i = 0; i < N; i++){
        int cost_i = cost[i];
        if(cost_i == -1) continue; // 필수 경찰서인 경우는 설치했으니 패스
        if((pSum + cost_i) / (pCnt + 1) < pSum / pCnt){
            pSum += cost_i;
            pCnt++;
        }
    }
    
    cout.precision(12);
    cout << fixed;
    
    cout << pSum / pCnt;
    return 0;
}

---

25트...

그래도 오랜만에 여러 생각을 하며 푼 재밌는 문제였습니다.