BOJ 백준 6672번 Electricity

 

BOJ 백준 6672 Electricity

문제: https://www.acmicpc.net/problem/6672

6672번: Electricity

 

 

 

처음에는 문제 내용을 제대로 이해하지 못해서 난처했는데, 결국 간단히 정리하면 주어진 네트워크에서 임의의 한 정점을 제거했을 때 최대 몇 개의 부분으로 나눠지는지를 구하는 문제이다.

 

트리에서의 다이나믹 프로그래밍(Dynamic Programming)으로 풀 수 있는 문제인 줄 알았는데, 문제에서 ‘The network may contain cycles.’이라고 명시되어 있다. 그래서 주어지는 네트워크 그래프가 트리가 아닐 수 있으므로 다른 접근 방법이 필요해보였다.

 

단순히 DFS(Depth Frist Search)를 통해 어떤 cycle 내의 임의의 한 점을 제거한다고 해서 cycle이 무조건 두 개 이상의 부분으로 나눠진다고 보장할 수 없다. 따라서 단절점의 개념을 이용하면 문제를 풀 수 있을 것이다.

 

하나의 컴포넌트(Connected Component)로 이루어진 양방향(또는 무방향) 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나눌 수 있을 때 그 정점이 단절점이다. 문제에서 주어진 그래프에서 단절점을 찾고, 그 중 하나를 제거했을 때 부분으로 나누어지는 컴포넌트 수를 구하면 될 것이다. 단절점이 아닌 정점을 제거하면 해당 정점이 속한 BCC(Biconnected Component)가 분리되지 않으므로 단절점에 관해서만 제거 시 몇 개의 부분으로 나누어지는지 확인하면 된다.

 

Tarjan’s Algorithm의 DFS 과정을 통해서 모든 정점을 방문해주는데, 그 중 방문 중인 현재 노드 now가 단절점일 때 해당 노드가 몇 개의 컴포넌트에 속하는지 구한다. 

 

bccNum[i]: 정점 i가 속하는 BCC 개수

 

 

 

1) 단절점인 현재 노드 now가 root 노드가 아닐 때 

 

bccNum[now] = (now 노드의 자식 노드와 묶이는 BCC 개수) + 1
∵ 부모 노드와 묶이는 BCC도 추가해야 하므로 1을 더한다.

 

※ 현재 노드 now의 부모 노드가 두 개 이상일 수도 있지 않을까?

 

- Tarjan’s Algorithm의 실행 과정을 이해하면 방문 중인 노드의 부모 노드가 두 개 이상일 수가 없다. Cycle이 있는 그래프를 DFS 탐색할 때 방문 중인 노드의 부모 노드를 두 개 이상으로 판단하고 탐색하지 않는 것과 유사하다.

 

 

 

2) 단절점인 현재 노드 now가 root 노드일 때

 

bccNum[now] = now 노드의 자식 노드와 묶이는 BCC 개수

 

 

 

전체 그래프에서 모든 정점의 bccNum 중 가장 큰 값을 답으로 구한다.

ans = max(bccNum[i]) (단, 정점 i는 단절점, 1 ≤ i ≤ v)

 

 

 

주의할 점은 애초에 처음부터 둘 이상의 컴포넌트로 분리되어 있는 그래프가 네트워크로 주어질 수도 있다는 것이다.

 

cnt: 정점 제거 전 전체 Connected Component 개수

 

 

 

cnt와 ans를 구한 후 ans에 최종적으로 cnt - 1을 더한다. 1을 빼준 이유는 삭제할 단절점이 반드시 분리 전의 하나의 컴포넌트에 속하므로 중복하여 세는 것을 피하기 위함이다.

 

ans = max(bccNum[i]) + cnt - 1

 

 

#include <cstdio>
#include <tuple>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
using pp = pair<int, int>;

// SCC 찾는 알고리즘과의 차이는
// 그래프가 양방향이 되면서의 생기는 결과

const int V_MAX = (int)1e4;

int v, e, visit, bccCnt;
int low[V_MAX];
int bccNum[V_MAX];
int discovered[V_MAX];

// 양방향 그래프여서 Cross Edge가 만들어질 수가 없으므로
// finished 배열 필요 없음

bool ap[V_MAX];

vector<int> edges[V_MAX];

void dfs(int now, int parent = -1){
    low[now] = discovered[now] = (++visit);
    
    for (auto next: edges[now]){
        if (next == parent){
            continue;
        }
        if (!discovered[next]){
            // Tree Edge에 관해서만 stack에 넣어주면 됨
            dfs(next, now);
            low[now] = min(low[now], low[next]);
            // Tree Edge에 따라 BCC가 나누어짐
            if (discovered[now] <= low[next]){
                bccNum[now] += 1;
                if (parent != -1){
                    ap[now] = true;
                }
            }
        }
        // 여기서는 Cross Edge와 Forward Edge가 존재할 수 없으므로
        // 조상으로 타고 올라가는 Edge인지만 판단함
        else if (discovered[next] < discovered[now]){
            low[now] = min(low[now], discovered[next]);
        }
    }
    // root 노드가 아니면서 단절점이면
    if (parent != -1 && ap[now]){
        bccNum[now] += 1;
    }
    if (parent == -1) {
        ap[now] = true;
    }
}

int main(){
    while(1){
        int v, e; scanf("%d %d", &v, &e);
        if (v == 0 && e == 0){
            break;
        }
        
        visit = bccCnt = 0;
        memset(low, 0, sizeof(low));
        memset(bccNum, 0, sizeof(bccNum));
        memset(discovered, 0, sizeof(discovered));
        memset(ap, false, sizeof(ap));
        
        for (int i = 0; i < v; i++){
            edges[i].clear();
        }
        
        for (int i = 0; i < e; i++){
            int a, b; scanf("%d %d", &a, &b);
            edges[a].push_back(b);
            edges[b].push_back(a);
        }
        
        int cnt = 0;
        for (int i = 0; i < v; i++){
            if (!discovered[i]){
                dfs(i);
                cnt += 1;
            }
        }
        
        int ans = 0;
        for (int i = 0; i < v; i++){
            if (ap[i]){
                ans = max(ans, bccNum[i] + cnt - 1);
            }
        }
        printf("%d\n", ans);
    }
    
    return 0;
}