산만한 고양이( BOJ 14866 )

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

14866번: 산만한 고양이

 

문제 파악하기

그래프의 사이클을 없애기 위해 제거해야 하는 정점을 찾는 문제입니다. 사이클을 이루는 정점마다 하나씩 제거해서 확인할 수 있지만, 정올 4번 문제답게 입력되는 정점의 개수가 300,000개로 어마어마합니다. 그렇기에 각각의 정점을 제거하는 O(n²) 알고리즘으로는 시간이 부족하며, 좀 더 효율적인 알고리즘이 필요합니다. 여기서 우리가 사용할 수 있는 유용한 개념은 바로 DFS 트리입니다.

 

문제 해결하기

DFS 트리란 그래프의 모든 정점을 방문하면서 만들어지는 경로를 의미합니다. 트리라는 자료구조는 항상 노드 N개에 대해 최대 (N-1)개의 간선을 가지게 됩니다. 따라서, 우리가 정점들을 방문하며 만든 DFS 트리 역시 최대 (N-1)개의 간선을 가지고 있습니다. 사실 여기까지는 대부분 알고 있으리라 생각하고, 우리가 진짜 초점을 맞출 간선은 바로 사용되지 않은 간선입니다. 그리고 우리는 이러한 무방향 그래프에서 DFS 트리에 포함되지 않은 간선을 역간선이라고 합니다. 역간선이라는 이름에서 눈치챌 수 있듯이, 이 간선은 현재 노드의 조상을 연결하는 간선으로, 우리는 역간선과 앞에서 이야기한 트리의 특징을 이용해서 문제를 해결할 수 있습니다.

 

트리는 결국 N개의 정점에 대해 가질 수 있는 간선의 개수가 최대 (N-1)개 입니다. 이 말은 어떤 그래프에 간선이 최대치보다 많다면 그 그래프는 무조건 트리가 아니라고 확신할 수 있습니다. 그럼 간선의 개수가 (N-1)개 이하라면 항상 트리일까요? 안타깝게도 정답은 거짓입니다. 단순히 간선의 개수로는 판단할 수 없습니다. 하지만, 우리는 여기에 서브그래프의 개수를 포함시키면 트리인지 확인할 수 있습니다. 서브그래프(부분 그래프)란 정점/간선을 제거했을 때, 나누어지는 그래프들을 의미합니다. 다행히 우리는 하나의 정점을 제거했을 때, 만들어지는 모든 서브그래프가 트리 형태여야 합니다. 따라서, 정점의 개수와 나누어진 서브그래프의 개수를 알고 있다면 모든 서브그래프가 트리가 되기 위해 필요한 최대 간선의 개수를 구할 수 있습니다.

 

최대 간선의 수  =   ( 정점의 수 ) - ( 서브그래프의 수 )

 

따라서 우리는 모든 정점에 대해 현재 탐색하는 정점을 제거했을 때, 만들어지는 서브그래프의 수를 구한 다음, 남아있는 간선의 개수를 확인하면서 제거해도 되는지 여부를 알 수 있습니다. 그럼 현재 정점을 제거하면 만들어지는 서브그래프의 수는 어떻게 구할 수 있을까요? 단순히 현재 노드의 자식의 수만큼일까요? 바로 역간선을 통해 확인할 수 있습니다. 만약, 자식노드에 역간선이 없거나 현재 노드까지 연결되었다면 현재 노드 제거 시, 그래프가 분리되게 됩니다. 하지만, 만약 어떤 자식 노드 중 하나가 현재 노드 위에 있는 조상노드를 가리키고 있는 역간선을 가지고 있다면 현재 노드를 제거해도 그래프는 분리되지 않습니다. 따라서, 우리는 가지고 있는 모든 자식노드의 역간선을 확인하고, 역간선이 가리키는 노드의 위치에 따라 서브그래프 수를 구할 수 있습니다. 다만, 현재 노드가 루트인지 아닌지에 따라 초깃값이 달라지는 예외처리 역시 필요합니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX 300010
using namespace std;
 
int N, M, a, b;
vector< int > graph[MAX];
 
int vi;
long long int cnt;
int visited[MAX], low[MAX], sub[MAX];
 
void dfs(int cur, int par) {
 
    // 루트가 아니라면 부모노드와의 간선을 끊어서 나눠질 수 있음
    if(par > 0) sub[cur] = 1;
 
    low[cur] = visited[cur] = ++vi;
    for(int nxt:graph[cur]) {
        if(par == nxt) continue;
 
        if(visited[nxt]) low[cur] = min( low[cur], low[nxt] );
        else {
            dfs(nxt, cur);
 
            low[cur] = min( low[cur], low[nxt] );
            if(low[nxt] >= visited[cur]) sub[cur]++;
        }
    }
 
    // (N-1)-sub[cur] : cur을 제거해서 만들어진 서브 그래프가 트리이기 위한 간선의 개수
    // M-graph[cur].size : 현재 사용하는 간선의 개수
    if((N-1)-sub[cur] >= M-graph[cur].size()) cnt += cur;
}
 
int main() {
    // 입력
    scanf("%d %d", &N, &M);
    for(int i=1;i<=M;i++) {
        scanf("%d %d", &a, &b);
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    // DFS를 통해 역간선 찾기
    dfs(1, 0);
 
    printf("%lld", cnt);
}
 
/*
8 11
1 7
8 1
3 2
8 6
2 1
6 2
2 7
3 7
4 7
7 5
1 6
ans: 0
*/

후기

간선의 개수와 트리와의 상관관계를 열심히 고민했던 문제입니다. 열심히 고민한 덕분에 트리와 간선, 그리고 역간선에 대해 실컷 공부하게 되어 뿌듯합니다. 트리 혹은 그래프를 공부하는 사람에게 추천하고 싶은 문제입니다.