[editorial] 2008년 ACM ICPC 서울대회 인터넷 예선 D번 Electric Network

  • wookayin
    wookayin

      D번 문제는 그래프 문제로, 관련 내용을 알고 있었다면 쉽게 접근할 수 있는 문제였지만 그렇지 않았다면 어려울 수도 있는 문제였습니다. 주최측의 통계에 따르면, 총 7팀이 풀었고(F나 H보다 적게 풀렸군요-..-) Correct Submissions / Total Submissions 는 약 26.9% 였다고 합니다.
      이 문제를 요약하면, 주어진 그래프가 'Doubly Linked' 되기 위해 추가해야 하는 최소 개수의 에지 수를 구하는 것이 됩니다. 어떤 그래프가 Doubly Linked 되었다 함은, 그래프를 동강내버리기 위해서는 최소 두 개의 간선을 끊어야 함을 의미합니다. 즉, 하나의 간선을 끊어서는 그래프를 분리할 수 없다는 것이지요. 그래프 이론에서는 이를 이중 연결(Biconnected)이라 합니다. 
      (다음 내용은 건너뛰시고 읽으셔도 됩니다)
      비슷한 것으로 Bi-vertex-connected 와 Bi-Edge-connected 라는 게 있습니다. Bi-vertex-connected 는 그래프에서 최소 2개의 점을 끊어야 그래프를 분리할 수 있는 경우이고, Bi-edge-connected 는 그래프에서 최소 2개의 간선을 끊어야 그래프를 분리할 수 있는 경우입니다.

    D0.gif

      문제의 그림에서 (a)는 Bi-Edge-connected Graph 이지만 Bi-Vertex-connected Graph 는 아닙니다. 가운데의 점 하나만을 제거해도 되니까요. 이러한 정점들을 절점(Articulation Points)라고 합니다. 마찬가지로 (b)는 Bi-Edge-Connected Graph 가 아닌데, 그 이유는 가운데의 절선 하나만 제거하면 그래프가 쪼개지기 때문입니다. 이러한 간선들을 절선(Bridges)라고 합니다. 이 문제에서 말하는 Doubly Linked 란 Bi-Edge-connected를 의미하는 것이지만, 이 글에서는 biconnected 라는 것을 bi-edge-connected 에 한정하여 사용하도록 하겠습니다 -0- (원래 아무 말 없이 Biconnected 라는 것은 Bi-Vertex-connected 를 의미합니다.)

      어떠한 그래프가 Biconnected 라면, 이 그래프에는 절점과 절선이 없습니다. 즉 이러한 그래프에는 간선을 추가할 필요가 없으므로, 이 그래프 요소들을 모아 하나의 정점으로 생각해 볼 수 있습니다. 이러한 것을 이중 연결 요소(Biconnected Components) 라고 합니다. 그렇다면, 임의의 그래프는 적당히 몇 개의 Biconnected Components 들로 나눌 수 있고, 이 Components 는 각각 하나의 정점이 되는데, 이 정점들을 갖고 만든 그래프는 항상 트리가 됩니다!

    D1.gif
      이 트리에서 어떤 두 점을 새로운 간선을 추가하여 잇게 되면, 그 두 점 사이에 있던 모든 점(요소)들은 Biconnected 가 됩니다. 트리에서 두 점 사이의 경로는 유일한데, 간선을 달게 되면 그 경로에 포함되는 모든 점들이 다 하나의 Biconected Compontents 에 들어가게 됩니다.

    D2.gif
      목적은 최소 개수의 간선을 이용하여 모든 그래프가 Biconnected 되게 하는 것이므로, 새로운 그래프에서 단말 노드끼리 이어주는게 최적이 된다는 것을 어렵지 않게 알 수 있습니다. 단말 노드가 2L개 있다면, 최소 L개의 간선을 추가해야 하는데 L개만 추가하면 그래프가 모두 이중 연결되므로 답이 L임을 알 수 있습니다. 만약 2L+1개 있다면, L+1개 추가해야 합니다. 즉, 이 그래프(트리)에서 단말 노드의 수를 L이라 할 때, 답은 int((L+1)/2) 가 됨을 알 수 있습니다. 단 모든 그래프가 하나의 이중 연결 요소가 된다면 답은 0이 되겠지요.
      결국 문제는 이중 연결 요소(절점/절선)를 구하는 알고리즘을 작성하는 것입니다. DFS를 사용하는 방법으로 시간복잡도 O(V+E)에 해결할 수 있습니다. 모든 것을 설명하기에는 너무 길기 때문에(....) 인터넷이나 책을 찾아보시면 될 것 같구요(예를 들면 여기), 간단하게 소개하자면, 다음과 같습니다.
      DFS를 하면 간선이 DFS-tree edge와 back edge 두 가지로 나뉘게 됩니다. 그렇다면

    dfsnum[u] : DFS 에서의 u 점의 방문 순서 low[u] = min{ dfsnum[u], dfsnum[v] : (u, v)는 back edge, low[v] : (u, v)는 tree edge}

    를 구할 수 있고, 어떤 간선이 절선이기 위해서는 tree edge (u, v)에 대하여 low[v] > dfstime[u] 이어야 합니다. 이렇게 DFS를 하고 나면 이중 연결 요소들을 분리해 낼 수 있고, 따라서 이를 갖고 새로운 그래프를 만들어 내시면 됩니다.

    Source Code
    n이 작기 때문에 인접행렬을 통해 O(n^2) 에 구현한 코드입니다. (인접리스트 등을 사용하면 O(N+M) 에 가능)

    #include 
    #include 
    #pragma warning(disable:4996)
    #define maxn 1001
    int n, m;
    bool w[maxn][maxn];    // 원래 그래프에서의 인접행렬
    bool isbridge[maxn][maxn];  // (u, v)가 절선이면 isbridge[u][v] = 1
    bool newgraph[maxn][maxn];  // 이중연결 요소들로 만든 그래프 (인접행렬)
    int newdegree[maxn];    // 그 그래프에서의 Degree
    int time = 0, bcc = 0;
    int low[maxn], dfstime[maxn];  // DFS 용 :)
    int bccgroup[maxn];        // i번 점이 bccgroup[i]번 요소에 포함됨.
    int que[maxn], qb, qf;      // BFS 용 :)
    void dfs(int u, int par = -1)
    {
      int v;
      low[u] = dfstime[u] = ++time;
      for(v=1; v<=n; ++v) if(w[u][v] && v != par)
      {
        if(!dfstime[v])
        {
          dfs(v, u);
          if(low[u] > low[v]) low[u] = low[v];
          // (u, v) 가 절선이 됩니다.
          if(low[v] > dfstime[u])
            isbridge[u][v] = isbridge[v][u] = 1;
        }
        else if(low[u] > dfstime[v])
          low[u] = dfstime[v];
      }
    }
    int main()
    {
      int t;
      scanf("%d", &t);
      while(t-- > 0)
      {
        scanf("%d %d", &n, &m);
        // 모든 배열을 초기화 합니다.
        memset(w, 0, sizeof(w));
        memset(isbridge, 0, sizeof(isbridge));
        memset(newgraph, 0, sizeof(newgraph));
        memset(newdegree, 0, sizeof(newdegree));
        memset(low, 0, sizeof(low));
        memset(bccgroup, 0, sizeof(bccgroup));
        memset(dfstime, 0, sizeof(dfstime));
        for(int i=0, x, y; i<=n; ++i) if(!bccgroup[i])
        {
          // bfs 를 통해 절선을 거치지 않고 갈 수 있는 점들을 하나의 bcc로 만듭니다.
          bccgroup[i] = ++bcc;
          qb = qf = 0; que[qb++] = i;
          while(qb != qf)
          {
            int u = que[qf++];
            for(int v=1; v<=n; ++v) if(w[u][v] && !isbridge[u][v] && !bccgroup[v])
            {
              bccgroup[v] = bcc;
              que[qb++] = v;
            }
          }
        }
        // 이중 연결 요소 (1..bcc)를 이용한 새로운 그래프를 만듭니다
        for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j)
        {
          if(w[i][j] && bccgroup[i] != bccgroup[j])
          {
            newgraph[ bccgroup[i] ][ bccgroup[j] ] = 1;
            newgraph[ bccgroup[j] ][ bccgroup[i] ] = 1;
          }
        }
        // terminal node 를 세기 위해, degree 를 셉니다.
        for(int i=1; i<=bcc; ++i) for(int j=i+1; j<=bcc; ++j)
        {
          if(newgraph[i][j])
          {
            newdegree[i] ++;
            newdegree[j] ++;
          }
        }
        // terminal nodes
        int terminal = 0;
        for(int i=1; i<=bcc; ++i)
          if(newdegree[i] == 1) terminal++;
        if(terminal == 1)
          printf("%d\n", 0);
        else printf("%d\n", (terminal + 1) / 2);
      }
      return 0;
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
2개의 댓글이 있습니다.
  • ibroker
    ibroker

    음. 이거 혹시 dfs내부에서 stack을 사용해서 dfs 돌면서 한번에 찾는 방법 아시는 분 계신가요?
    그 방법을 알고 싶은데 찾기가 힘드네요 ㅜ
    혹시 코드 갖고계시거나 알고리즘 아시는 분 있으면 알려주시면 감사하겠습니다. ^^


    13년 전 link
  • hyunhwan
    hyunhwan

    PKU 3177번 문제가 아마 biconnected component 문제였는데, 예전에 이걸 못풀다가 솔루션을 찾았었는데 도움이 되실련지는 모르겠네요. 일단 첨부해봅니다.

    #include <iostream>
    #include <fstream>
    #include <algorithm>
    #include <climits>
    #include <cassert>
    #include <vector>
    #include <cstddef>
    #include <stack>
    using namespace std;
    #define MAXC 5000
    #define MAXR 10000
    struct road {
        int target;
        int dual;
        road() {}
        road(int _target, int _dual) : target(_target), dual(_dual) {}
    };
    struct castle {
        int id;
        int top;
        int parent;
        int bcc;
        vector<road> roads;
        castle() : id(-1), top(-1), parent(-1), bcc(-1), roads() {}
    };
    static int C;
    static castle castles[MAXC];
    static bool connected() {
        stack<int> todo;
        vector<bool> seen(C, false);
        int remain = C;
        todo.push(0);
        seen[0] = true;
        while (!todo.empty()) {
            int cur = todo.top();
            todo.pop();
            remain--;
            seen[cur] = true;
            for (size_t i = 0; i < castles[cur].roads.size(); i++) {
                int nxt = castles[cur].roads[i].target;
                if (!seen[nxt]) {
                    todo.push(nxt);
                    seen[nxt] = true;
                }
            }
        }
        return remain == 0;
    }
    static void readin() {
        int R, x, y;
        cin >> C >> R;
        assert(3 <= C && C <= MAXC);
        assert(C - 1 <= R && R <= MAXR);
        for (int i = 0; i < R; i++) {
            cin >> x >> y;
            assert(x != y);
            assert(1 <= x && x <= C);
            assert(1 <= y && y <= C);
            x--;
            y--;
            castles[x].roads.push_back(road(y, castles[y].roads.size()));
            castles[y].roads.push_back(road(x, castles[x].roads.size() - 1));
        }
        assert(connected());
    }
    static int recurse(int cur, int up_edge) {
        static int id_pool = 0;
        static stack<int> bcc;
        int leaves = 0;
        castles[cur].id = id_pool++;
        castles[cur].top = cur;
        bcc.push(cur);
        for (size_t i = 0; i < castles[cur].roads.size(); i++) {
            int nxt = castles[cur].roads[i].target;
            if ((int) i == up_edge) continue;
            if (castles[nxt].id == -1) {
                castles[nxt].parent = cur;
                leaves += recurse(nxt, castles[cur].roads[i].dual);
            }
            if (castles[castles[nxt].top].id < castles[castles[cur].top].id)
                castles[cur].top = castles[nxt].top;
        }
        if (castles[cur].top == cur) {
            while (bcc.top() != cur) {
                castles[bcc.top()].bcc = cur;
                bcc.pop();
            }
            castles[cur].bcc = cur;
            bcc.pop();
            if (leaves == 0) leaves = 1;
        }
        return leaves;
    }
    static bool bridge(int c, int edge) {
        return castles[c].top == c && castles[c].roads[edge].target == castles[c].parent;
    }
    static int solve() {
        int leaves = recurse(0, -1);
        int root_children = 0;
        for (int i = 1; i < C; i++) {
            int p = castles[i].parent;
            if (castles[i].top == i && castles[p].bcc == 0) root_children++;
        }
        if (root_children == 0) return 0;
        else if (root_children == 1) leaves++;
        return (leaves + 1) / 2;
    }
    int main() {
        readin();
        cout << solve() << "\n";
        return 0;
    }
    

    13년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.